[niffiwan]

Swifty's go_even_faster patch has highlighted a problem with the way that the Linux/OSX FSO debug builds track the used memory.  In short, the current method is *painfully* slow at realloc's & free's when there are lots of memory allocations being tracked.  Therefore I came up with the following which (theoretically & in my testing) works a lot faster.  Could some kind people running a) 32bit Linux or b) OSX give this patch a go and check that everything still works normally?  Code review from all is also appreciated.

Note: this only affects debug builds, there's no point in testing this with a release build (assuming that I haven't seriously screwed up)

Code: [Select]

commit a5ebf3e2f801dc9e393669507a6cb196aafea189
Author: niffiwan <[email protected]>
Date:   Mon Aug 6 19:40:31 2012 +1000

    Replace RamTable memory management with something a bit faster

Index: fs2_open/code/windows_stub/stubs.cpp
===================================================================
--- fs2_open/code/windows_stub/stubs.cpp    (revision 9069)
+++ fs2_open/code/windows_stub/stubs.cpp    (working copy)
@@ -533,17 +533,9 @@ void strlwr(char *s)
  *
  * *************************************/
 
-// RamTable stuff comes out of icculus.org
-#ifndef NDEBUG
-typedef struct RAM {
- ptr_u addr;
- int size;
-
- RAM *next;
-} RAM;
-
-static RAM *RamTable;
-#endif
+// RamTable stuff replaced due to slow performance when freeing large amounts of memory
+// new method is based on this approach:
+// http://stackoverflow.com/questions/852072/simple-c-implementation-to-track-memory-malloc-free?lq=1
 
 int vm_init(int min_heap_size)
 {
@@ -560,7 +552,11 @@ void *_vm_malloc( int size, char *filename, int line, int quiet )
 void *_vm_malloc( int size, int quiet )
 #endif
 {
+#ifndef NDEBUG
+ void *ptr = malloc( size + sizeof(size_t) );
+#else
  void *ptr = malloc( size );
+#endif
 
  if (!ptr) {
  if (quiet) {
@@ -575,15 +571,11 @@ void *_vm_malloc( int size, int quiet )
  mprintf(( "Malloc %d bytes [%s(%d)]\n", size, clean_filename(filename), line ));
  }
 
- RAM *next = (RAM *)malloc(sizeof(RAM));
-
- next->addr = (ptr_u)ptr;
- next->size = (size + sizeof(RAM));
-
- next->next = RamTable;
- RamTable = next;
-
  TotalRam += size;
+
+ size_t *ptr_size = (size_t *)ptr;
+ memcpy(ptr_size, &size, sizeof(size));
+ ptr = (void *)++ptr_size;
 #endif
 
  return ptr;
@@ -598,7 +590,15 @@ void *_vm_realloc( void *ptr, int size, int quiet )
  if (ptr == NULL)
  return vm_malloc(size);
 
+#ifndef NDEBUG
+ size_t new_size = size + sizeof(size_t);
+ size_t *ptr_size = (size_t *)ptr;
+ --ptr_size;
+ size_t old_size = *ptr_size;
+ void *ret_ptr = realloc( ptr_size, new_size );
+#else
  void *ret_ptr = realloc( ptr, size );
+#endif
 
  if (!ret_ptr) {
  if (quiet && (size > 0) && (ptr != NULL)) {
@@ -610,16 +610,11 @@ void *_vm_realloc( void *ptr, int size, int quiet )
  }
 
 #ifndef NDEBUG
- RAM *item = RamTable;
+ TotalRam += (new_size - old_size);
 
- while (item != NULL) {
- if (item->addr == (ptr_u)ret_ptr) {
- TotalRam += (size - item->size);
- item->size = size;
- break;
- }
- item = item->next;
-    }
+ ptr_size = (size_t *)ret_ptr;
+ memcpy (ptr_size, &new_size, sizeof(new_size));
+ ret_ptr = (void *)++ptr_size;
 #endif
 
  return ret_ptr;
@@ -680,26 +675,10 @@ void _vm_free( void *ptr )
  }
 
 #ifndef NDEBUG
- RAM *item = RamTable;
-    RAM **mark = &RamTable;
-
- while (item != NULL) {
- if (item->addr == (ptr_u)ptr) {
- RAM *tmp = item;
-
- *mark = item->next;
-
- TotalRam -= tmp->size;
-
- free(tmp);
-
- break;
- }
-
- mark = &(item->next);
-
- item = item->next;
-    }
+ size_t *ptr_size = (size_t *)ptr;
+ --ptr_size;
+ TotalRam -= *ptr_size;
+ ptr = (void *)ptr_size;
 #endif // !NDEBUG
 
  free(ptr);

[attachment removed and sold on the black market]

[Echelon9]

Simple approach, but we should be careful that this approach doesn't lead to wasteful memory allocations at effective sizes greater than power-of-two - a class of bugs given the title of "clown shoes" by the Mozilla Firefox memshrink team.

In particular, by adding this tracking size_t bytes, are we for example leading to allocations for malloc(1024) to be found to, say, return the result of malloc(2056), because we are asking for malloc(1024 + X)?

For more reference see the SQLite bug found by Mozilla, http://blog.mozilla.org/nnethercote/2011/08/05/clownshoes-available-in-sizes-2101-and-up/

[niffiwan]

Thanks for the feedback.  I'll have a look through the code to see if we're trying to malloc on power of 2 sizes anywhere.  I presume that if we're not already being careful with this, then we're probably already hitting this issue with our normal mallocs() and the added size_t bytes to each allocation will only have a small chance (by itself) of causing this issue.  Although STL vectors (and friends) could be taking allocating on power of 2 sizes with their under-the-hood memory allocations... profiling in valgrind would probably be a better way to investigate this.

In addition, I'll change the stored malloc() size to include the allocation overhead.

[niffiwan]

After some more investigation, I've redone the patch to use malloc_usable_size() & malloc_size() - these functions are designed for dynamic memory allocation introspection.  Although it seems that the chances of "clownshoes" was fairly low, this change will ensure that it is no worse that it is currently.

Any feedback will be appreciated 

[attachment removed and sold on the black market]

[Echelon9]

Thanks, will take a look.

Niffiwan has done some good testing offline to run this possible issue to ground.

[Echelon9]

Looks fine from my testing.

[niffiwan]

Thanks for the review, committed in r9128