new home directory
[feisty_meow.git] / nucleus / library / application / memory_checker.cpp
1
2
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : memory_checker                                                    *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1998-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 // note: parts of this have been around since at least 1998, but this code was
19 // newly revised for memory checking in february of 2007.  --cak
20
21 #ifdef ENABLE_MEMORY_HOOK
22
23 #include "definitions.h"
24 #include "log_base.h"
25 #include "memory_checker.h"
26 #include "mutex.h"
27 #include "utility.h"
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32
33 const int MAXIMUM_HASH_SLOTS = 256 * KILOBYTE;
34   // that's a whole lot of slots.  this number is basically multiplied by
35   // the sizeof(memory_bin) to get full memory footprint.
36
37 const int SINGLE_LINE_SIZE_ESTIMATE = 200;
38   // we are guessing that the average line of memory printout will take
39   // this many characters.  that includes the size, the pointer value,
40   // and the location and line number.
41
42 const int RESERVED_AREA = 1000;
43   // we reserve this much space in the string generated for the memory bin
44   // dumps.  it will be used for adding more information to the string.
45
46 #define CLEAR_ALLOCATED_MEMORY
47   // uncomment this to ensure that new memory gets its contents set to zero.
48   // neither new nor malloc does this, but it can help finding bugs from
49   // people re-using deallocated memory.
50
51 #define MEMORY_CHECKER_STATISTICS
52   // uncomment to enable code that analyzes how many allocations were new and
53   // so forth.  this will make the object run a bit slower.
54
55 //#define DEBUG_MEMORY_CHECKER
56   // uncomment for super noisy version.
57
58 //////////////
59
60 // define the replacement new and delete operators.
61
62 #include <basis/trap_new.addin>
63 void *operator new(size_t size, char *file, int line) throw (std::bad_alloc)
64 { return program_wide_memories().provide_memory(size, file, line); }
65 #include <basis/untrap_new.addin>
66
67 void operator delete(void *ptr) throw ()
68 { program_wide_memories().release_memory(ptr); }
69
70 //////////////
71
72 // memlink is one link in a chain of memories.  it's singly linked, so our
73 // algorithms have to explicitly remember the parent.
74
75 class memlink
76 {
77 public:
78   void *_chunk;  //!< the chunk of memory held (not real address).
79     /*!< NOTE: we store the chunk as it looks to the outside world, rather
80     than using its real address.  this eliminates a bit of ambiguity in the
81     code. */
82   memlink *_next;  //!< the next memory wrapper in the list.
83   int _size;  //!< the size of the chunk delivered.
84   char *_where;  //!< the name of the place that created it.
85   int _line;  //!< the line number where the item was allocated.
86 #ifdef ENABLE_CALLSTACK_TRACKING
87   char *_stack;  //!< records the stack seen at time of allocation.
88 #endif
89
90   void construct(void *ptr, int size, char *where, int line) {
91     _next = NULL_POINTER;
92     _chunk = ptr;
93     _size = size;
94     _where = strdup(where);  // uses malloc, not new, so we're safe.
95     if (strlen(_where) > SINGLE_LINE_SIZE_ESTIMATE - 40) {
96       // if we will not have room for the full line, we crop it.
97       _where[SINGLE_LINE_SIZE_ESTIMATE - 40] = '\0';
98     }
99     _line = line;
100 #ifdef ENABLE_CALLSTACK_TRACKING
101     _stack = program_wide_stack_trace().full_trace();
102 ///printf("stack here:\n%s", _stack);
103 #endif
104   }
105
106   void destruct() {
107     free(_chunk); _chunk = NULL_POINTER;
108     free(_where); _where = NULL_POINTER; 
109     _next = NULL_POINTER;
110     _size = 0;
111     _line = 0;
112 #ifdef ENABLE_CALLSTACK_TRACKING
113     free(_stack); _stack = NULL_POINTER;
114 #endif
115   }
116 };
117
118 //////////////
119
120 //pretty lame here so far.
121 #ifdef MEMORY_CHECKER_STATISTICS
122   // simple stats: the methods below will tweak these numbers if memory_checker
123   // statistics are enabled.  ints won't do here, due to the number of
124   // operations in a long-running program easily overflowing that size.
125
126   // this bank of statistics counts the number of times memory was treated
127   // a certain way.
128   double _stat_new_allocations = 0;  // this many new allocations occurred.
129   double _stat_freed_allocations = 0;  // number of freed blocks.
130   // next bank of stats are the sizes of the memory that were stowed, etc.
131   double _stat_new_allocations_size = 0;  // this many bytes got allocated.
132   double _stat_freed_allocations_size = 0;  // this many bytes were freed.
133 #endif
134
135 //////////////
136
137 //! the memory bin holds a list of chunks of memory in memlink objects.
138
139 class memory_bin
140 {
141 public:
142   void construct() {
143     _head = NULL_POINTER;
144     _count = 0;
145     _lock = (mutex_base *)malloc(sizeof(mutex_base));
146     _lock->construct();
147   }
148   void destruct() {
149     _lock->destruct();
150     free(_lock);
151   }
152
153   int count() const { return _count; }
154
155   int record_memory(void *ptr, int size, char *where, int line) {
156     memlink *new_guy = (memlink *)malloc(sizeof(memlink));
157     new_guy->construct(ptr, size, where, line);
158     _lock->lock();
159     // this code has the effect of putting more recent allocations first.
160     // if they happen to get cleaned up right away, that's nice and fast.
161     new_guy->_next = _head;
162     _head = new_guy;
163     _count++;
164     _lock->unlock();
165     return common::OKAY;  // seems to have worked fine.
166   }
167
168   int release_memory(void *to_release) {
169     _lock->lock();
170     // search the bin to locate the item specified.
171     memlink *current = _head;  // current will scoot through the list.
172     memlink *previous = NULL_POINTER;  // previous remembers the parent node, if any.
173     while (current) {
174       if (current->_chunk == to_release) {
175 #ifdef MEMORY_CHECKER_STATISTICS
176         // record that it went away.
177         _stat_freed_allocations += 1.0;
178         _stat_freed_allocations_size += current->_size;
179 #endif
180 #ifdef DEBUG_MEMORY_CHECKER
181         printf("found %p listed, removing for %s[%d]\n", to_release,
182             current->_where, current->_line);
183 #endif
184         // unlink this one and clean up; they don't want it now.
185         if (!previous) {
186           // this is the head we're modifying.
187           _head = current->_next;
188         } else {
189           // not the head, so there was a valid previous element.
190           previous->_next = current->_next;
191         }
192         // now trash that goner's house.
193         current->destruct();
194         free(current);
195         _count--;
196         _lock->unlock();
197         return common::OKAY;
198       }
199       // the current node isn't it; jump to next node.
200       previous = current;
201       current = current->_next;
202     }
203 #ifdef DEBUG_MEMORY_CHECKER
204     printf("failed to find %p listed.\n", to_release);
205 #endif
206     _lock->unlock();
207     return common::NOT_FOUND;
208   }
209
210   void dump_list(char *add_to, int &curr_size, int max_size) {
211     int size_alloc = 2 * SINGLE_LINE_SIZE_ESTIMATE;  // room for one line.
212     char *temp_str = (char *)malloc(size_alloc);
213     memlink *current = _head;  // current will scoot through the list.
214     while (current) {
215       temp_str[0] = '\0';
216       sprintf(temp_str, "\n\"%s[%d]\", \"size %d\", \"addr %p\"\n",
217           current->_where, current->_line, current->_size, current->_chunk);
218       int len_add = strlen(temp_str);
219       if (curr_size + len_add < max_size) {
220         strcat(add_to, temp_str);
221         curr_size += len_add;
222       }
223 #ifdef ENABLE_CALLSTACK_TRACKING
224       len_add = strlen(current->_stack);
225       if (curr_size + len_add < max_size) {
226         strcat(add_to, current->_stack);
227         curr_size += len_add;
228       }
229 #endif
230       current = current->_next;
231     }
232     free(temp_str);
233   }
234
235 private:
236   memlink *_head;  // our first, if any, item.
237   mutex_base *_lock;  // protects our bin from concurrent access.
238   int _count;  // current count of items held.
239 };
240
241 //////////////
242
243 class allocation_memories
244 {
245 public:
246   void construct(int num_slots) {
247     _num_slots = num_slots;
248     _bins = (memory_bin *)malloc(num_slots * sizeof(memory_bin));
249     for (int i = 0; i < num_slots; i++)
250       _bins[i].construct();
251   }
252
253   void destruct() {
254     // destroy each bin in our list.
255     for (int i = 0; i < _num_slots; i++) {
256       _bins[i].destruct();
257     }
258     free(_bins);
259     _bins = NULL_POINTER;
260   }
261
262   int compute_slot(void *ptr) {
263     return utility::hash_bytes(&ptr, sizeof(void *)) % _num_slots;
264   }
265
266   void *provide_memory(int size_needed, char *file, int line) {
267     void *new_allocation = malloc(size_needed);
268     // slice and dice pointer to get appropriate hash bin.
269     int slot = compute_slot(new_allocation);
270 #ifdef DEBUG_MEMORY_CHECKER
271     printf("using slot %d for %p\n", slot, new_allocation);
272 #endif
273     _bins[slot].record_memory(new_allocation, size_needed, file, line);
274 #ifdef MEMORY_CHECKER_STATISTICS
275     _stat_new_allocations += 1.0;
276     _stat_new_allocations_size += size_needed;
277 #endif
278     return new_allocation;
279   }
280
281   int release_memory(void *to_drop) {
282     int slot = compute_slot(to_drop);  // slice and dice to get bin number.
283 #ifdef DEBUG_MEMORY_CHECKER
284     printf("removing mem %p from slot %d.\n", to_drop, slot);
285 #endif
286     return _bins[slot].release_memory(to_drop);
287   }
288
289   //! this returns a newly created string with all current contents listed.
290   /*! this returns a simple char * pointer that was created with malloc.
291   the invoker *must* free the returned pointer.  we use malloc/free here to
292   avoid creating a wacky report that contains a lot of new allocations for
293   the report itself.  that seems like it could become a problem. */
294   char *report_allocations() {
295     // count how many allocations we have overall.
296     int full_count = 0;
297     for (int i = 0; i < _num_slots; i++) {
298 ///if (_bins[i].count()) printf("%d adding count %d\n", i, _bins[i].count());
299       full_count += _bins[i].count();
300     }
301 ///printf("full count is %d\n", full_count);
302     // calculate a guess for how much space we need to show all of those.
303     int alloc_size = full_count * SINGLE_LINE_SIZE_ESTIMATE + RESERVED_AREA;
304     char *to_return = (char *)malloc(alloc_size);
305     to_return[0] = '\0';
306     if (full_count) {
307       strcat(to_return, "===================\n");
308       strcat(to_return, "Unfreed Allocations\n");
309       strcat(to_return, "===================\n");
310     }
311     int curr_size = strlen(to_return);  // how much in use so far.
312     for (int i = 0; i < _num_slots; i++) {
313       _bins[i].dump_list(to_return, curr_size, alloc_size - RESERVED_AREA);
314     }
315     return to_return;
316   }
317
318   // this is fairly resource intensive, so don't dump the state out that often.
319   char *text_form(bool show_outstanding) {
320     char *to_return = NULL_POINTER;
321     if (show_outstanding) {
322       to_return = report_allocations();
323     } else {
324       to_return = (char *)malloc(RESERVED_AREA);
325       to_return[0] = '\0';
326     }
327 #ifdef MEMORY_CHECKER_STATISTICS
328     char *temp_str = (char *)malloc(4 * SINGLE_LINE_SIZE_ESTIMATE);
329     
330     sprintf(temp_str, "=================\n");
331     strcat(to_return, temp_str);
332     sprintf(temp_str, "Memory Statistics\n");
333     strcat(to_return, temp_str);
334     sprintf(temp_str, "=================\n");
335     strcat(to_return, temp_str);
336     sprintf(temp_str, "Measurements taken across entire program runtime:\n");
337     strcat(to_return, temp_str);
338     sprintf(temp_str, "  %.0f new allocations.\n", _stat_new_allocations);
339     strcat(to_return, temp_str);
340     sprintf(temp_str, "  %.4f new Mbytes.\n",
341         _stat_new_allocations_size / MEGABYTE);
342     strcat(to_return, temp_str);
343     sprintf(temp_str, "  %.0f freed deallocations.\n",
344         _stat_freed_allocations);
345     strcat(to_return, temp_str);
346     sprintf(temp_str, "  %.4f freed Mbytes.\n",
347         _stat_freed_allocations_size / MEGABYTE);
348     strcat(to_return, temp_str);
349
350     free(temp_str);
351 #endif
352     return to_return;
353   }
354
355 private:
356   memory_bin *_bins;  //!< each bin manages a list of pointers, found by hash.
357   int _num_slots;  //!< the number of hash slots we have.
358 };
359
360 //////////////
361
362 void memory_checker::construct()
363 {
364   _mems = (allocation_memories *)malloc(sizeof(allocation_memories));
365   _mems->construct(MAXIMUM_HASH_SLOTS);
366   _unusable = false;
367   _enabled = true;
368 }
369
370 void memory_checker::destruct()
371 {
372   if (_unusable) return;  // already gone.
373 if (!_mems) printf("memory_checker::destruct being invoked twice!\n");
374
375   // show some stats about memory allocation.
376   char *mem_state = text_form(true);
377   printf("%s", mem_state);
378 ///uhhh  free(mem_state);
379 //the above free seems to totally die if we allow it to happen.
380
381   _unusable = true;
382
383   _mems->destruct();
384   free(_mems);
385   _mems = NULL_POINTER;
386 }
387
388 void *memory_checker::provide_memory(size_t size, char *file, int line)
389 {
390   if (_unusable || !_enabled) return malloc(size);
391   return _mems->provide_memory(size, file, line);
392 }
393
394 int memory_checker::release_memory(void *ptr)
395 {
396   if (_unusable || !_enabled) {
397     free(ptr);
398     return common::OKAY;
399   }
400   return _mems->release_memory(ptr);
401 }
402
403 char *memory_checker::text_form(bool show_outstanding)
404 {
405   if (_unusable) return strdup("already destroyed memory_checker!\n");
406   return _mems->text_form(show_outstanding);
407 }
408
409 //////////////
410
411 #endif  // enable memory hook
412
413
414