BRL-CAD
heap.c
Go to the documentation of this file.
1 /* H E A P . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2013-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdlib.h> /* for getenv, atoi, and atexit */
24 
25 #include "bu/debug.h"
26 #include "bu/log.h"
27 #include "bu/malloc.h"
28 #include "bu/parallel.h"
29 #include "bu/vls.h"
30 
31 /**
32  * This number specifies the range of byte sizes to support for fast
33  * memory allocations. Any request outside this range will get passed
34  * to bu_calloc().
35  *
36  * 1-to-HEAP_BINS byte size allocations are allocated in PAGESIZE chunks as
37  * they are requested. There's minimal penalty for making this
38  * arbitrarily large except where there are very few allocations (each
39  * size will allocate at least one page). PAGESIZE should be some
40  * multiple larger than HEAP_BINS.
41  *
42  * Embedded or memory-constrained environments probably want to set
43  * this a lot smaller than the default.
44  */
45 #define HEAP_BINS 256
46 
47 /**
48  * This specifies how much memory we should preallocate for each
49  * allocation size. Note that this number should be some multiple of
50  * HEAP_BINS and system page size in order to be useful. Ideally sized to
51  * keep the allocation size with the most requests down to
52  * single-digit page counts. Testing showed a 1M page size was very
53  * effective at eliminating allocation overhead.
54  *
55  * Embedded or memory-constrained environments probably want to set
56  * this a lot smaller than the default.
57  */
58 #define HEAP_PAGESIZE (HEAP_BINS * 256)
59 
60 
61 struct heap {
62  /**
63  * pages is an array of memory pages. they are allocated one at a
64  * time so we only have to keep track of the last page.
65  */
66  char **pages;
67 
68  /**
69  * a count of how many heap pages have been allocated so we can
70  * quickly jump into the current.
71  */
72  size_t count;
73 
74  /**
75  * given tabulates how much memory the current page has been
76  * allocated to callers. not a counter to avoid a multiply.
77  */
78  size_t given;
79 };
80 
81 struct cpus {
82  /** each allocation size gets a bin for holding memory pages */
83  struct heap heap[HEAP_BINS];
84 
85  /** keep track of allocation sizes outside our supported range */
86  size_t misses;
87 };
88 
89 /**
90  * store data in a cpu-specific structure so we can avoid the need for
91  * mutex locking entirely. relies on static zero-initialization.
92  */
93 static struct cpus per_cpu[MAX_PSW] = {{{{0, 0, 0}}, 0}};
94 
95 
98 {
99  static bu_heap_func_t heap_log = (bu_heap_func_t)&bu_log;
100 
101  if (log)
102  heap_log = log;
103 
104  return heap_log;
105 }
106 
107 
108 static void
109 heap_print(void)
110 {
111  static int printed = 0;
112 
113  size_t h, i;
114  size_t allocs = 0;
115  size_t misses = 0;
116  size_t got = 0;
117  size_t total_pages = 0;
118  size_t ncpu = bu_avail_cpus();
119 
120  bu_heap_func_t log = bu_heap_log(NULL);
121 
122  struct bu_vls str = BU_VLS_INIT_ZERO;
123 
124  /* this may get atexit()-registered multiple times, so make sure
125  * we only do this once
126  */
127  if (printed++ > 0) {
128  return;
129  }
130 
131  log("=======================\n"
132  "Memory Heap Information\n"
133  "-----------------------\n", NULL);
134 
135  for (h=0; h < ncpu; h++) {
136  for (i=0; i < HEAP_BINS; i++) {
137 
138  /* capacity across all pages */
139  got = per_cpu[h].heap[i].count * (HEAP_PAGESIZE/(i+1));
140 
141  if (got > 0) {
142  /* last page is partial */
143  got -= (HEAP_PAGESIZE - per_cpu[h].heap[i].given)/(i+1);
144  bu_vls_sprintf(&str, "%04zu [%02zu] => %zu\n", i, per_cpu[h].heap[i].count, got);
145  log(bu_vls_addr(&str), NULL);
146  allocs += got;
147  }
148  total_pages += per_cpu[h].heap[i].count;
149  }
150  misses += per_cpu[h].misses;
151  }
152  bu_vls_sprintf(&str, "-----------------------\n"
153  "size [pages] => count\n"
154  "Heap range: 1-%d bytes\n"
155  "Page size: %d bytes\n"
156  "Pages: %zu (%.2lfMB)\n"
157  "%zu allocs, %zu misses\n"
158  "=======================\n",
159  HEAP_BINS,
161  total_pages,
162  (double)(total_pages * HEAP_PAGESIZE) / (1024.0*1024.0),
163  allocs,
164  misses);
165  log(bu_vls_addr(&str), NULL);
166  bu_vls_free(&str);
167 }
168 
169 
170 void *
171 bu_heap_get(size_t sz)
172 {
173  char *ret;
174  register size_t smo = sz-1;
175  static int registered = 0;
176  int oncpu;
177  struct heap *heap;
178 
179  /* what thread are we? */
180  oncpu = bu_parallel_id();
181 
182 #ifdef DEBUG
183  if (sz > HEAP_BINS || sz == 0) {
184  per_cpu[oncpu].misses++;
185 
186  if (bu_debug) {
187  bu_log("DEBUG: heap size %zd out of range\n", sz);
188 
190  bu_bomb("Intentionally bombing due to BU_DEBUG_COREDUMP and BU_DEBUG_MEM_CHECK\n");
191  }
192  }
193  return bu_calloc(1, sz, "heap calloc");
194  }
195 #endif
196 
197  heap = &per_cpu[oncpu].heap[smo];
198 
199  /* init */
200  if (heap->count == 0) {
201 
202  if (registered++ == 0) {
203  ret = getenv("BU_HEAP_PRINT");
204  if ((++registered == 2) && (ret && atoi(ret) > 0)) {
205  atexit(heap_print);
206  }
207  }
208 
209  heap->count++;
210  heap->pages = (char **)bu_malloc(1 * sizeof(char *), "heap malloc pages[]");
211  heap->pages[0] = (char *)bu_calloc(1, HEAP_PAGESIZE, "heap calloc pages[][0]");
212  heap->given = 0;
213  }
214 
215  /* grow */
216  if (heap->given+sz > HEAP_PAGESIZE) {
217  heap->count++;
218  heap->pages = (char **)bu_realloc(heap->pages, heap->count * sizeof(char *), "heap realloc pages[]");
219  heap->pages[heap->count-1] = (char *)bu_calloc(1, HEAP_PAGESIZE, "heap calloc pages[][]");
220  heap->given = 0;
221  }
222 
223  /* give */
224  ret = &(heap->pages[heap->count-1][heap->given]);
225  heap->given += sz;
226 
227  return (void *)ret;
228 }
229 
230 
231 void
232 bu_heap_put(void *ptr, size_t sz)
233 {
234  if (sz > HEAP_BINS || sz == 0) {
235  bu_free(ptr, "heap free");
236  return;
237  }
238 
239  /* TODO: actually do something useful :) */
240 
241  return;
242 }
243 
244 
245 /* sanity */
246 #if HEAP_PAGESIZE < HEAP_BINS
247 # error "ERROR: heap page size cannot be smaller than bin range"
248 #endif
249 
250 
251 /*
252  * Local Variables:
253  * tab-width: 8
254  * mode: C
255  * indent-tabs-mode: t
256  * c-file-style: "stroustrup"
257  * End:
258  * ex: shiftwidth=4 tabstop=8
259  */
struct heap heap[HEAP_BINS]
Definition: heap.c:83
size_t misses
Definition: heap.c:86
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
Definition: heap.c:61
#define BU_DEBUG_MEM_CHECK
Definition: debug.h:54
size_t given
Definition: heap.c:78
char ** pages
Definition: heap.c:66
Header file for the BRL-CAD common definitions.
#define HEAP_PAGESIZE
Definition: heap.c:58
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
void bu_heap_put(void *ptr, size_t sz)
Definition: heap.c:232
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
void bu_vls_sprintf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:707
int bu_parallel_id(void)
Definition: parallel.c:152
void * bu_realloc(void *ptr, size_t siz, const char *str)
size_t count
Definition: heap.c:72
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
Definition: heap.c:81
#define BU_DEBUG_COREDUMP
Definition: debug.h:53
size_t bu_avail_cpus(void)
Definition: parallel.c:193
#define MAX_PSW
Definition: parallel.h:48
bu_heap_func_t bu_heap_log(bu_heap_func_t log)
Definition: heap.c:97
int bu_debug
Definition: globals.c:87
int(* bu_heap_func_t)(const char *,...)
Definition: malloc.h:166
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
void * bu_heap_get(size_t sz)
Definition: heap.c:171
Definition: vls.h:56
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define HEAP_BINS
Definition: heap.c:45