Post #2505356

2025-09-10 19:39 UTC

As it happens, we still use CVS in our operating system project (there are reasons for doing this, but migration to git would indeed make sense). While working on our project, we occasionally have to do a full checkout of the whole codebase, which is several gigabytes. Over time, this operation has gotten very, very, very slow - I mean &quot;2+ hours to perform a checkout&quot; slow. This was getting quite ridiculous. Even though it&#39;s CVS, it shouldn&#39;t crawl like this. A quick build of CVS with debug symbols and sampling the &quot;cvs server&quot; process with Linux perf showed something peculiar: The code was spending the majority of the time inside one function. So what is this get_memnode() function? Turns out this is a support function from Gnulib that enables page-aligned memory allocations. (NOTE: I have no clue why CVS thinks doing page-aligned allocations is beneficial here - but here we are.) The code in question has support for three different backend allocators: 1. mmap 2. posix_memalign 3. malloc Sounds nice, except that both 1 and 3 use a linked list to track the allocations. The get_memnode() function is called when deallocating memory to find out the original pointer to pass to the backend deallocation function: The node search code appears as: for (c = *p_next; c != NULL; p_next = &amp;c-&gt;next, c = c-&gt;next) if (c-&gt;aligned_ptr == aligned_ptr) break; The get_memnode() function is called from pagealign_free(): #if HAVE_MMAP if (munmap (aligned_ptr, get_memnode (aligned_ptr)) &lt; 0) error (EXIT_FAILURE, errno, &quot;Failed to unmap memory&quot;); #elif HAVE_POSIX_MEMALIGN free (aligned_ptr); #else free (get_memnode (aligned_ptr)); #endif This is an O(n) operation. CVS must be allocating a huge number of small allocations, which will result in it spending most of the CPU time in get_memnode() trying to find the node to remove from the list. Why should we care? This is &quot;just CVS&quot; after all. Well, Gnulib is used in a lot of projects, not just CVS. While pagealign_alloc() is likely not the most used functionality, it can still end up hurting performance in many places. The obvious easy fix is to prefer the posix_memalign method over the other options (I quickly made this happen for my personal CVS build by adding tactical #undef HAVE_MMAP). Even better, the list code should be replaced with something more sensible. In fact, there is no need to store the original pointer in a list; a better solution is to allocate enough memory and store the pointer before the calculated aligned pointer. This way, the original pointer can be fetched from the negative offset of the pointer passed to pagealign_free(). This way, it will be O(1). I tried to report this to the Gnulib project, but I have trouble reaching gnu.org services currently. I&#39;ll be sure to do that once things recover. #opensource #development #bugstories

Replies (7)

@harrysintonen@infosec.exchange 2025-09-10 20:48

The code in question is mirrored here https://github.com/coreutils/gnulib/blob/3aca72031cf0f856c3354df64570358c929263ca/lib/pagealign_alloc.c

Open ##2942458
@harrysintonen@infosec.exchange 2025-09-10 20:55

Presumably mmap should always return pagesize aligned memory, so it is a bit puzzling why the mmap codepath uses the list at all. Possibly an oversight there as well?

Open ##2942459
@harrysintonen@infosec.exchange 2025-09-10 21:33

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.

Open ##2942460
@harrysintonen@infosec.exchange 2025-09-11 10:13

The fix to Gnulib is here: https://cgit.git.savannah.gnu.org/cgit/gnulib.git/commit/?id=7c96b402be00117225a6943ab53bb9e5e6e2c02b The most clean solution was to prefer posix_memalign over mmap. It was also pointed out that according to POSIX, mmap can return non-pagesize-aligned pointers, making my idea of avoiding the use of the list for the USE_MMAP case non-portable. It'd work for most platforms, but it could then break for some. This is something that Gnulib, of course, cannot do. Another idea was to use some more suitable data structure with a sensible search performance over the linked list. However, using a more exotic data structure (hash, tree, etc.) would likely be a bit of overkill and wasn't deemed worth the amount of code complexity it'd add. Finally, placing the allocation pointer in a negative offset of the aligned pointer would lead to significant allocation overhead due to it having to allocate at least one extra full page worth of memory - at least if the code would need to stay portable, as is the case with Gnulib.

Open ##2942462
@joncruz@mstdn.social 2025-09-11 02:16

@harrysintonen@infosec.exchange 😱

Open ##2942463
@gnomon@mastodon.social 2025-09-11 04:11

@harrysintonen@infosec.exchange this is an excellent write-up, thank you!

Open ##2942464
@aperezdc@oldbytes.space 2025-09-11 18:30

@harrysintonen@infosec.exchange very nice writeup, this reads like a post from https://www.tumblr.com/accidentallyquadratic — too bad it hasn't received updates since 2019, because surely there's more issues lurking in the corners of many software projects.

Open ##2942465