![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ngx_slab.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core|
Return to ngx_slab.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core |
1.1 misho 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: }