Post #2942460

So how does CVS use pagealign_xalloc? Like this: /* Allocate more buffer_data structures. */ /* Get a new buffer_data structure. */ static struct buffer_data * get_buffer_data (void) { struct buffer_data *ret; ret = xmalloc (sizeof (struct buffer_data)); ret->text = pagealign_xalloc (BUFFER_DATA_SIZE); return ret; } Surely BUFFER_DATA_SIZE will be something sensible? Unfortunately it is not: #define BUFFER_DATA_SIZE getpagesize () 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? The pagealign code stores new nodes always to the head of its list: new_node->next = memnode_table; memnode_table = new_node; The datanodes in CVS code are however inserted into a list tail: newdata = get_buffer_data (); if (newdata == NULL) { (*buf->memory_error) (buf); return; } if (buf->data == NULL) buf->data = newdata; else buf->last->next = newdata; newdata->next = NULL; buf->last = newdata; 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: static inline void buf_free_datas (struct buffer_data *first, struct buffer_data *last) { struct buffer_data *b, *n, *p; b = first; do { p = b; n = b->next; pagealign_free (b->text); free (b); b = n; } while (p != last); } In short: This is very bad. It will be slow as heck as soon as large amounts of data is processed by this code. 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. 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. This gives 137438691328 iterations.