Groonga 3.0.9 Source Code Document
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
ngx_slab.c
Go to the documentation of this file.
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) Nginx, Inc.
5  */
6 
7 #include <ngx_config.h>
8 #include <ngx_core.h>
9 
10 
11 #define NGX_SLAB_PAGE_MASK 3
12 #define NGX_SLAB_PAGE 0
13 #define NGX_SLAB_BIG 1
14 #define NGX_SLAB_EXACT 2
15 #define NGX_SLAB_SMALL 3
16 
17 #if (NGX_PTR_SIZE == 4)
18 
19 #define NGX_SLAB_PAGE_FREE 0
20 #define NGX_SLAB_PAGE_BUSY 0xffffffff
21 #define NGX_SLAB_PAGE_START 0x80000000
22 
23 #define NGX_SLAB_SHIFT_MASK 0x0000000f
24 #define NGX_SLAB_MAP_MASK 0xffff0000
25 #define NGX_SLAB_MAP_SHIFT 16
26 
27 #define NGX_SLAB_BUSY 0xffffffff
28 
29 #else /* (NGX_PTR_SIZE == 8) */
30 
31 #define NGX_SLAB_PAGE_FREE 0
32 #define NGX_SLAB_PAGE_BUSY 0xffffffffffffffff
33 #define NGX_SLAB_PAGE_START 0x8000000000000000
34 
35 #define NGX_SLAB_SHIFT_MASK 0x000000000000000f
36 #define NGX_SLAB_MAP_MASK 0xffffffff00000000
37 #define NGX_SLAB_MAP_SHIFT 32
38 
39 #define NGX_SLAB_BUSY 0xffffffffffffffff
40 
41 #endif
42 
43 
44 #if (NGX_DEBUG_MALLOC)
45 
46 #define ngx_slab_junk(p, size) ngx_memset(p, 0xA5, size)
47 
48 #elif (NGX_HAVE_DEBUG_MALLOC)
49 
50 #define ngx_slab_junk(p, size) \
51  if (ngx_debug_malloc) ngx_memset(p, 0xA5, size)
52 
53 #else
54 
55 #define ngx_slab_junk(p, size)
56 
57 #endif
58 
59 static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool,
60  ngx_uint_t pages);
61 static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
62  ngx_uint_t pages);
63 static void ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level,
64  char *text);
65 
66 
67 static ngx_uint_t ngx_slab_max_size;
68 static ngx_uint_t ngx_slab_exact_size;
69 static ngx_uint_t ngx_slab_exact_shift;
70 
71 
72 void
73 ngx_slab_init(ngx_slab_pool_t *pool)
74 {
75  u_char *p;
76  size_t size;
77  ngx_int_t m;
78  ngx_uint_t i, n, pages;
79  ngx_slab_page_t *slots;
80 
81  /* STUB */
82  if (ngx_slab_max_size == 0) {
83  ngx_slab_max_size = ngx_pagesize / 2;
84  ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
85  for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
86  /* void */
87  }
88  }
89 
90 
91  pool->min_size = 1 << pool->min_shift;
92 
93  p = (u_char *) pool + sizeof(ngx_slab_pool_t);
94  size = pool->end - p;
95 
96  ngx_slab_junk(p, size);
97 
98  slots = (ngx_slab_page_t *) p;
99  n = ngx_pagesize_shift - pool->min_shift;
100 
101  for (i = 0; i < n; i++) {
102  slots[i].slab = 0;
103  slots[i].next = &slots[i];
104  slots[i].prev = 0;
105  }
106 
107  p += n * sizeof(ngx_slab_page_t);
108 
109  pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));
110 
111  ngx_memzero(p, pages * sizeof(ngx_slab_page_t));
112 
113  pool->pages = (ngx_slab_page_t *) p;
114 
115  pool->free.prev = 0;
116  pool->free.next = (ngx_slab_page_t *) p;
117 
118  pool->pages->slab = pages;
119  pool->pages->next = &pool->free;
120  pool->pages->prev = (uintptr_t) &pool->free;
121 
122  pool->start = (u_char *)
123  ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
124  ngx_pagesize);
125 
126  m = pages - (pool->end - pool->start) / ngx_pagesize;
127  if (m > 0) {
128  pages -= m;
129  pool->pages->slab = pages;
130  }
131 
132  pool->log_ctx = &pool->zero;
133  pool->zero = '\0';
134 }
135 
136 
137 void *
138 ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
139 {
140  void *p;
141 
142  ngx_shmtx_lock(&pool->mutex);
143 
144  p = ngx_slab_alloc_locked(pool, size);
145 
146  ngx_shmtx_unlock(&pool->mutex);
147 
148  return p;
149 }
150 
151 
152 void *
153 ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
154 {
155  size_t s;
156  uintptr_t p, n, m, mask, *bitmap;
157  ngx_uint_t i, slot, shift, map;
158  ngx_slab_page_t *page, *prev, *slots;
159 
160  if (size >= ngx_slab_max_size) {
161 
162  ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
163  "slab alloc: %uz", size);
164 
165  page = ngx_slab_alloc_pages(pool, (size >> ngx_pagesize_shift)
166  + ((size % ngx_pagesize) ? 1 : 0));
167  if (page) {
168  p = (page - pool->pages) << ngx_pagesize_shift;
169  p += (uintptr_t) pool->start;
170 
171  } else {
172  p = 0;
173  }
174 
175  goto done;
176  }
177 
178  if (size > pool->min_size) {
179  shift = 1;
180  for (s = size - 1; s >>= 1; shift++) { /* void */ }
181  slot = shift - pool->min_shift;
182 
183  } else {
184  size = pool->min_size;
185  shift = pool->min_shift;
186  slot = 0;
187  }
188 
189  ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
190  "slab alloc: %uz slot: %ui", size, slot);
191 
192  slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));
193  page = slots[slot].next;
194 
195  if (page->next != page) {
196 
197  if (shift < ngx_slab_exact_shift) {
198 
199  do {
200  p = (page - pool->pages) << ngx_pagesize_shift;
201  bitmap = (uintptr_t *) (pool->start + p);
202 
203  map = (1 << (ngx_pagesize_shift - shift))
204  / (sizeof(uintptr_t) * 8);
205 
206  for (n = 0; n < map; n++) {
207 
208  if (bitmap[n] != NGX_SLAB_BUSY) {
209 
210  for (m = 1, i = 0; m; m <<= 1, i++) {
211  if ((bitmap[n] & m)) {
212  continue;
213  }
214 
215  bitmap[n] |= m;
216 
217  i = ((n * sizeof(uintptr_t) * 8) << shift)
218  + (i << shift);
219 
220  if (bitmap[n] == NGX_SLAB_BUSY) {
221  for (n = n + 1; n < map; n++) {
222  if (bitmap[n] != NGX_SLAB_BUSY) {
223  p = (uintptr_t) bitmap + i;
224 
225  goto done;
226  }
227  }
228 
229  prev = (ngx_slab_page_t *)
230  (page->prev & ~NGX_SLAB_PAGE_MASK);
231  prev->next = page->next;
232  page->next->prev = page->prev;
233 
234  page->next = NULL;
235  page->prev = NGX_SLAB_SMALL;
236  }
237 
238  p = (uintptr_t) bitmap + i;
239 
240  goto done;
241  }
242  }
243  }
244 
245  page = page->next;
246 
247  } while (page);
248 
249  } else if (shift == ngx_slab_exact_shift) {
250 
251  do {
252  if (page->slab != NGX_SLAB_BUSY) {
253 
254  for (m = 1, i = 0; m; m <<= 1, i++) {
255  if ((page->slab & m)) {
256  continue;
257  }
258 
259  page->slab |= m;
260 
261  if (page->slab == NGX_SLAB_BUSY) {
262  prev = (ngx_slab_page_t *)
263  (page->prev & ~NGX_SLAB_PAGE_MASK);
264  prev->next = page->next;
265  page->next->prev = page->prev;
266 
267  page->next = NULL;
268  page->prev = NGX_SLAB_EXACT;
269  }
270 
271  p = (page - pool->pages) << ngx_pagesize_shift;
272  p += i << shift;
273  p += (uintptr_t) pool->start;
274 
275  goto done;
276  }
277  }
278 
279  page = page->next;
280 
281  } while (page);
282 
283  } else { /* shift > ngx_slab_exact_shift */
284 
285  n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
286  n = 1 << n;
287  n = ((uintptr_t) 1 << n) - 1;
288  mask = n << NGX_SLAB_MAP_SHIFT;
289 
290  do {
291  if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {
292 
293  for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
294  m & mask;
295  m <<= 1, i++)
296  {
297  if ((page->slab & m)) {
298  continue;
299  }
300 
301  page->slab |= m;
302 
303  if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
304  prev = (ngx_slab_page_t *)
305  (page->prev & ~NGX_SLAB_PAGE_MASK);
306  prev->next = page->next;
307  page->next->prev = page->prev;
308 
309  page->next = NULL;
310  page->prev = NGX_SLAB_BIG;
311  }
312 
313  p = (page - pool->pages) << ngx_pagesize_shift;
314  p += i << shift;
315  p += (uintptr_t) pool->start;
316 
317  goto done;
318  }
319  }
320 
321  page = page->next;
322 
323  } while (page);
324  }
325  }
326 
327  page = ngx_slab_alloc_pages(pool, 1);
328 
329  if (page) {
330  if (shift < ngx_slab_exact_shift) {
331  p = (page - pool->pages) << ngx_pagesize_shift;
332  bitmap = (uintptr_t *) (pool->start + p);
333 
334  s = 1 << shift;
335  n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;
336 
337  if (n == 0) {
338  n = 1;
339  }
340 
341  bitmap[0] = (2 << n) - 1;
342 
343  map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
344 
345  for (i = 1; i < map; i++) {
346  bitmap[i] = 0;
347  }
348 
349  page->slab = shift;
350  page->next = &slots[slot];
351  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
352 
353  slots[slot].next = page;
354 
355  p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
356  p += (uintptr_t) pool->start;
357 
358  goto done;
359 
360  } else if (shift == ngx_slab_exact_shift) {
361 
362  page->slab = 1;
363  page->next = &slots[slot];
364  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
365 
366  slots[slot].next = page;
367 
368  p = (page - pool->pages) << ngx_pagesize_shift;
369  p += (uintptr_t) pool->start;
370 
371  goto done;
372 
373  } else { /* shift > ngx_slab_exact_shift */
374 
375  page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
376  page->next = &slots[slot];
377  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
378 
379  slots[slot].next = page;
380 
381  p = (page - pool->pages) << ngx_pagesize_shift;
382  p += (uintptr_t) pool->start;
383 
384  goto done;
385  }
386  }
387 
388  p = 0;
389 
390 done:
391 
392  ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);
393 
394  return (void *) p;
395 }
396 
397 
398 void
399 ngx_slab_free(ngx_slab_pool_t *pool, void *p)
400 {
401  ngx_shmtx_lock(&pool->mutex);
402 
403  ngx_slab_free_locked(pool, p);
404 
405  ngx_shmtx_unlock(&pool->mutex);
406 }
407 
408 
409 void
410 ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p)
411 {
412  size_t size;
413  uintptr_t slab, m, *bitmap;
414  ngx_uint_t n, type, slot, shift, map;
415  ngx_slab_page_t *slots, *page;
416 
417  ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);
418 
419  if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
420  ngx_slab_error(pool, NGX_LOG_ALERT, "ngx_slab_free(): outside of pool");
421  goto fail;
422  }
423 
424  n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
425  page = &pool->pages[n];
426  slab = page->slab;
427  type = page->prev & NGX_SLAB_PAGE_MASK;
428 
429  switch (type) {
430 
431  case NGX_SLAB_SMALL:
432 
433  shift = slab & NGX_SLAB_SHIFT_MASK;
434  size = 1 << shift;
435 
436  if ((uintptr_t) p & (size - 1)) {
437  goto wrong_chunk;
438  }
439 
440  n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
441  m = (uintptr_t) 1 << (n & (sizeof(uintptr_t) * 8 - 1));
442  n /= (sizeof(uintptr_t) * 8);
443  bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));
444 
445  if (bitmap[n] & m) {
446 
447  if (page->next == NULL) {
448  slots = (ngx_slab_page_t *)
449  ((u_char *) pool + sizeof(ngx_slab_pool_t));
450  slot = shift - pool->min_shift;
451 
452  page->next = slots[slot].next;
453  slots[slot].next = page;
454 
455  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
456  page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
457  }
458 
459  bitmap[n] &= ~m;
460 
461  n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);
462 
463  if (n == 0) {
464  n = 1;
465  }
466 
467  if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
468  goto done;
469  }
470 
471  map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
472 
473  for (n = 1; n < map; n++) {
474  if (bitmap[n]) {
475  goto done;
476  }
477  }
478 
479  ngx_slab_free_pages(pool, page, 1);
480 
481  goto done;
482  }
483 
484  goto chunk_already_free;
485 
486  case NGX_SLAB_EXACT:
487 
488  m = (uintptr_t) 1 <<
489  (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
490  size = ngx_slab_exact_size;
491 
492  if ((uintptr_t) p & (size - 1)) {
493  goto wrong_chunk;
494  }
495 
496  if (slab & m) {
497  if (slab == NGX_SLAB_BUSY) {
498  slots = (ngx_slab_page_t *)
499  ((u_char *) pool + sizeof(ngx_slab_pool_t));
500  slot = ngx_slab_exact_shift - pool->min_shift;
501 
502  page->next = slots[slot].next;
503  slots[slot].next = page;
504 
505  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
506  page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
507  }
508 
509  page->slab &= ~m;
510 
511  if (page->slab) {
512  goto done;
513  }
514 
515  ngx_slab_free_pages(pool, page, 1);
516 
517  goto done;
518  }
519 
520  goto chunk_already_free;
521 
522  case NGX_SLAB_BIG:
523 
524  shift = slab & NGX_SLAB_SHIFT_MASK;
525  size = 1 << shift;
526 
527  if ((uintptr_t) p & (size - 1)) {
528  goto wrong_chunk;
529  }
530 
531  m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
532  + NGX_SLAB_MAP_SHIFT);
533 
534  if (slab & m) {
535 
536  if (page->next == NULL) {
537  slots = (ngx_slab_page_t *)
538  ((u_char *) pool + sizeof(ngx_slab_pool_t));
539  slot = shift - pool->min_shift;
540 
541  page->next = slots[slot].next;
542  slots[slot].next = page;
543 
544  page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
545  page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
546  }
547 
548  page->slab &= ~m;
549 
550  if (page->slab & NGX_SLAB_MAP_MASK) {
551  goto done;
552  }
553 
554  ngx_slab_free_pages(pool, page, 1);
555 
556  goto done;
557  }
558 
559  goto chunk_already_free;
560 
561  case NGX_SLAB_PAGE:
562 
563  if ((uintptr_t) p & (ngx_pagesize - 1)) {
564  goto wrong_chunk;
565  }
566 
567  if (slab == NGX_SLAB_PAGE_FREE) {
568  ngx_slab_error(pool, NGX_LOG_ALERT,
569  "ngx_slab_free(): page is already free");
570  goto fail;
571  }
572 
573  if (slab == NGX_SLAB_PAGE_BUSY) {
574  ngx_slab_error(pool, NGX_LOG_ALERT,
575  "ngx_slab_free(): pointer to wrong page");
576  goto fail;
577  }
578 
579  n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
580  size = slab & ~NGX_SLAB_PAGE_START;
581 
582  ngx_slab_free_pages(pool, &pool->pages[n], size);
583 
584  ngx_slab_junk(p, size << ngx_pagesize_shift);
585 
586  return;
587  }
588 
589  /* not reached */
590 
591  return;
592 
593 done:
594 
595  ngx_slab_junk(p, size);
596 
597  return;
598 
599 wrong_chunk:
600 
601  ngx_slab_error(pool, NGX_LOG_ALERT,
602  "ngx_slab_free(): pointer to wrong chunk");
603 
604  goto fail;
605 
606 chunk_already_free:
607 
608  ngx_slab_error(pool, NGX_LOG_ALERT,
609  "ngx_slab_free(): chunk is already free");
610 
611 fail:
612 
613  return;
614 }
615 
616 
617 static ngx_slab_page_t *
618 ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
619 {
620  ngx_slab_page_t *page, *p;
621 
622  for (page = pool->free.next; page != &pool->free; page = page->next) {
623 
624  if (page->slab >= pages) {
625 
626  if (page->slab > pages) {
627  page[pages].slab = page->slab - pages;
628  page[pages].next = page->next;
629  page[pages].prev = page->prev;
630 
631  p = (ngx_slab_page_t *) page->prev;
632  p->next = &page[pages];
633  page->next->prev = (uintptr_t) &page[pages];
634 
635  } else {
636  p = (ngx_slab_page_t *) page->prev;
637  p->next = page->next;
638  page->next->prev = page->prev;
639  }
640 
641  page->slab = pages | NGX_SLAB_PAGE_START;
642  page->next = NULL;
643  page->prev = NGX_SLAB_PAGE;
644 
645  if (--pages == 0) {
646  return page;
647  }
648 
649  for (p = page + 1; pages; pages--) {
650  p->slab = NGX_SLAB_PAGE_BUSY;
651  p->next = NULL;
652  p->prev = NGX_SLAB_PAGE;
653  p++;
654  }
655 
656  return page;
657  }
658  }
659 
660  ngx_slab_error(pool, NGX_LOG_CRIT, "ngx_slab_alloc() failed: no memory");
661 
662  return NULL;
663 }
664 
665 
666 static void
667 ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
668  ngx_uint_t pages)
669 {
670  ngx_slab_page_t *prev;
671 
672  page->slab = pages--;
673 
674  if (pages) {
675  ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
676  }
677 
678  if (page->next) {
679  prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
680  prev->next = page->next;
681  page->next->prev = page->prev;
682  }
683 
684  page->prev = (uintptr_t) &pool->free;
685  page->next = pool->free.next;
686 
687  page->next->prev = (uintptr_t) page;
688 
689  pool->free.next = page;
690 }
691 
692 
693 static void
694 ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level, char *text)
695 {
696  ngx_log_error(level, ngx_cycle->log, 0, "%s%s", text, pool->log_ctx);
697 }
Generated on Sun Nov 10 2013 09:49:07 for Groonga 3.0.9 Source Code Document by   doxygen 1.8.1.2