Harry Sintonen<p>So how does CVS use pagealign_xalloc? Like this:</p><p>/* Allocate more buffer_data structures. */<br>/* Get a new buffer_data structure. */<br>static struct buffer_data *<br>get_buffer_data (void)<br>{<br> struct buffer_data *ret;</p><p> ret = xmalloc (sizeof (struct buffer_data));<br> ret->text = pagealign_xalloc (BUFFER_DATA_SIZE);</p><p> return ret;<br>}</p><p>Surely BUFFER_DATA_SIZE will be something sensible? Unfortunately it is not:</p><p><a href="https://infosec.exchange/tags/define" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>define</span></a> BUFFER_DATA_SIZE getpagesize ()</p><p>So it will by create total_data_size / pagesize number of list nodes in the linear list. Maybe it's not that bad if the nodes are released in an optimal order?</p><p>The pagealign code stores new nodes always to the head of its list:</p><p> new_node->next = memnode_table;<br> memnode_table = new_node;</p><p>The datanodes in CVS code are however inserted into a list tail:</p><p> newdata = get_buffer_data ();<br> if (newdata == NULL)<br> {<br> (*buf->memory_error) (buf);<br> return;<br> }</p><p> if (buf->data == NULL)<br> buf->data = newdata;<br> else<br> buf->last->next = newdata;<br> newdata->next = NULL;<br> buf->last = newdata;</p><p>This creates a pathological situation where the nodes in the aligned list are in worst possible order as buf_free_datas() walks the internal list in first to last node, calling the pagealign_free:</p><p>static inline void<br>buf_free_datas (struct buffer_data *first, struct buffer_data *last)<br>{<br> struct buffer_data *b, *n, *p;<br> b = first;<br> do<br> {<br> p = b;<br> n = b->next;<br> pagealign_free (b->text);<br> free (b);<br> b = n;<br> } while (p != last);<br>}</p><p>In short: This is very bad. It will be slow as heck as soon as large amounts of data is processed by this code.</p><p>So imagine you have 2GB buffer allocated by using this code on a system that has 4KB pagesize. This would result in 524288 nodes. Each node would be stored in two lists, in first one they're last-head and in the other they're last-tail.</p><p>When the buf_free_datas is called for this buffer, it will walk totalnodes - index pagealign nodes for each of the released nodes. First iteration is (524288 - 1) "unnecessary" node walks, second (524288 - 2) and so forth. In other terms "sum of all integers smaller than itself", so in total totalnodes * (totalnodes - 1) / 2 extra operations.</p><p>This gives 137438691328 iterations.</p>