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#define ngx_slab_slots(pool)                                                  \
45    (ngx_slab_page_t *) ((u_char *) (pool) + sizeof(ngx_slab_pool_t))
46
47#define ngx_slab_page_type(page)   ((page)->prev & NGX_SLAB_PAGE_MASK)
48
49#define ngx_slab_page_prev(page)                                              \
50    (ngx_slab_page_t *) ((page)->prev & ~NGX_SLAB_PAGE_MASK)
51
52#define ngx_slab_page_addr(pool, page)                                        \
53    ((((page) - (pool)->pages) << ngx_pagesize_shift)                         \
54     + (uintptr_t) (pool)->start)
55
56
57#if (NGX_DEBUG_MALLOC)
58
59#define ngx_slab_junk(p, size)     ngx_memset(p, 0xA5, size)
60
61#elif (NGX_HAVE_DEBUG_MALLOC)
62
63#define ngx_slab_junk(p, size)                                                \
64    if (ngx_debug_malloc)          ngx_memset(p, 0xA5, size)
65
66#else
67
68#define ngx_slab_junk(p, size)
69
70#endif
71
72static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool,
73    ngx_uint_t pages);
74static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
75    ngx_uint_t pages);
76static void ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level,
77    char *text);
78
79
80static ngx_uint_t  ngx_slab_max_size;
81static ngx_uint_t  ngx_slab_exact_size;
82static ngx_uint_t  ngx_slab_exact_shift;
83
84
85void
86ngx_slab_init(ngx_slab_pool_t *pool)
87{
88    u_char           *p;
89    size_t            size;
90    ngx_int_t         m;
91    ngx_uint_t        i, n, pages;
92    ngx_slab_page_t  *slots, *page;
93
94    /* STUB */
95    if (ngx_slab_max_size == 0) {
96        ngx_slab_max_size = ngx_pagesize / 2;
97        ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
98        for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
99            /* void */
100        }
101    }
102    /**/
103
104    pool->min_size = (size_t) 1 << pool->min_shift;
105
106    slots = ngx_slab_slots(pool);
107
108    p = (u_char *) slots;
109    size = pool->end - p;
110
111    ngx_slab_junk(p, size);
112
113    n = ngx_pagesize_shift - pool->min_shift;
114
115    for (i = 0; i < n; i++) {
116        /* only "next" is used in list head */
117        slots[i].slab = 0;
118        slots[i].next = &slots[i];
119        slots[i].prev = 0;
120    }
121
122    p += n * sizeof(ngx_slab_page_t);
123
124    pool->stats = (ngx_slab_stat_t *) p;
125    ngx_memzero(pool->stats, n * sizeof(ngx_slab_stat_t));
126
127    p += n * sizeof(ngx_slab_stat_t);
128
129    size -= n * (sizeof(ngx_slab_page_t) + sizeof(ngx_slab_stat_t));
130
131    pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));
132
133    pool->pages = (ngx_slab_page_t *) p;
134    ngx_memzero(pool->pages, pages * sizeof(ngx_slab_page_t));
135
136    page = pool->pages;
137
138    /* only "next" is used in list head */
139    pool->free.slab = 0;
140    pool->free.next = page;
141    pool->free.prev = 0;
142
143    page->slab = pages;
144    page->next = &pool->free;
145    page->prev = (uintptr_t) &pool->free;
146
147    pool->start = ngx_align_ptr(p + pages * sizeof(ngx_slab_page_t),
148                                ngx_pagesize);
149
150    m = pages - (pool->end - pool->start) / ngx_pagesize;
151    if (m > 0) {
152        pages -= m;
153        page->slab = pages;
154    }
155
156    pool->last = pool->pages + pages;
157    pool->pfree = pages;
158
159    pool->log_nomem = 1;
160    pool->log_ctx = &pool->zero;
161    pool->zero = '\0';
162}
163
164
165void *
166ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
167{
168    void  *p;
169
170    ngx_shmtx_lock(&pool->mutex);
171
172    p = ngx_slab_alloc_locked(pool, size);
173
174    ngx_shmtx_unlock(&pool->mutex);
175
176    return p;
177}
178
179
180void *
181ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
182{
183    size_t            s;
184    uintptr_t         p, n, m, mask, *bitmap;
185    ngx_uint_t        i, slot, shift, map;
186    ngx_slab_page_t  *page, *prev, *slots;
187
188    if (size > ngx_slab_max_size) {
189
190        ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
191                       "slab alloc: %uz", size);
192
193        page = ngx_slab_alloc_pages(pool, (size >> ngx_pagesize_shift)
194                                          + ((size % ngx_pagesize) ? 1 : 0));
195        if (page) {
196            p = ngx_slab_page_addr(pool, page);
197
198        } else {
199            p = 0;
200        }
201
202        goto done;
203    }
204
205    if (size > pool->min_size) {
206        shift = 1;
207        for (s = size - 1; s >>= 1; shift++) { /* void */ }
208        slot = shift - pool->min_shift;
209
210    } else {
211        shift = pool->min_shift;
212        slot = 0;
213    }
214
215    pool->stats[slot].reqs++;
216
217    ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
218                   "slab alloc: %uz slot: %ui", size, slot);
219
220    slots = ngx_slab_slots(pool);
221    page = slots[slot].next;
222
223    if (page->next != page) {
224
225        if (shift < ngx_slab_exact_shift) {
226
227            bitmap = (uintptr_t *) ngx_slab_page_addr(pool, page);
228
229            map = (ngx_pagesize >> shift) / (sizeof(uintptr_t) * 8);
230
231            for (n = 0; n < map; n++) {
232
233                if (bitmap[n] != NGX_SLAB_BUSY) {
234
235                    for (m = 1, i = 0; m; m <<= 1, i++) {
236                        if (bitmap[n] & m) {
237                            continue;
238                        }
239
240                        bitmap[n] |= m;
241
242                        i = (n * sizeof(uintptr_t) * 8 + i) << shift;
243
244                        p = (uintptr_t) bitmap + i;
245
246                        pool->stats[slot].used++;
247
248                        if (bitmap[n] == NGX_SLAB_BUSY) {
249                            for (n = n + 1; n < map; n++) {
250                                if (bitmap[n] != NGX_SLAB_BUSY) {
251                                    goto done;
252                                }
253                            }
254
255                            prev = ngx_slab_page_prev(page);
256                            prev->next = page->next;
257                            page->next->prev = page->prev;
258
259                            page->next = NULL;
260                            page->prev = NGX_SLAB_SMALL;
261                        }
262
263                        goto done;
264                    }
265                }
266            }
267
268        } else if (shift == ngx_slab_exact_shift) {
269
270            for (m = 1, i = 0; m; m <<= 1, i++) {
271                if (page->slab & m) {
272                    continue;
273                }
274
275                page->slab |= m;
276
277                if (page->slab == NGX_SLAB_BUSY) {
278                    prev = ngx_slab_page_prev(page);
279                    prev->next = page->next;
280                    page->next->prev = page->prev;
281
282                    page->next = NULL;
283                    page->prev = NGX_SLAB_EXACT;
284                }
285
286                p = ngx_slab_page_addr(pool, page) + (i << shift);
287
288                pool->stats[slot].used++;
289
290                goto done;
291            }
292
293        } else { /* shift > ngx_slab_exact_shift */
294
295            mask = ((uintptr_t) 1 << (ngx_pagesize >> shift)) - 1;
296            mask <<= NGX_SLAB_MAP_SHIFT;
297
298            for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
299                 m & mask;
300                 m <<= 1, i++)
301            {
302                if (page->slab & m) {
303                    continue;
304                }
305
306                page->slab |= m;
307
308                if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
309                    prev = ngx_slab_page_prev(page);
310                    prev->next = page->next;
311                    page->next->prev = page->prev;
312
313                    page->next = NULL;
314                    page->prev = NGX_SLAB_BIG;
315                }
316
317                p = ngx_slab_page_addr(pool, page) + (i << shift);
318
319                pool->stats[slot].used++;
320
321                goto done;
322            }
323        }
324
325        ngx_slab_error(pool, NGX_LOG_ALERT, "ngx_slab_alloc(): page is busy");
326        ngx_debug_point();
327    }
328
329    page = ngx_slab_alloc_pages(pool, 1);
330
331    if (page) {
332        if (shift < ngx_slab_exact_shift) {
333            bitmap = (uintptr_t *) ngx_slab_page_addr(pool, page);
334
335            n = (ngx_pagesize >> shift) / ((1 << shift) * 8);
336
337            if (n == 0) {
338                n = 1;
339            }
340
341            /* "n" elements for bitmap, plus one requested */
342            bitmap[0] = ((uintptr_t) 2 << n) - 1;
343
344            map = (ngx_pagesize >> shift) / (sizeof(uintptr_t) * 8);
345
346            for (i = 1; i < map; i++) {
347                bitmap[i] = 0;
348            }
349
350            page->slab = shift;
351            page->next = &slots[slot];
352            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
353
354            slots[slot].next = page;
355
356            pool->stats[slot].total += (ngx_pagesize >> shift) - n;
357
358            p = ngx_slab_page_addr(pool, page) + (n << shift);
359
360            pool->stats[slot].used++;
361
362            goto done;
363
364        } else if (shift == ngx_slab_exact_shift) {
365
366            page->slab = 1;
367            page->next = &slots[slot];
368            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
369
370            slots[slot].next = page;
371
372            pool->stats[slot].total += sizeof(uintptr_t) * 8;
373
374            p = ngx_slab_page_addr(pool, page);
375
376            pool->stats[slot].used++;
377
378            goto done;
379
380        } else { /* shift > ngx_slab_exact_shift */
381
382            page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
383            page->next = &slots[slot];
384            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
385
386            slots[slot].next = page;
387
388            pool->stats[slot].total += ngx_pagesize >> shift;
389
390            p = ngx_slab_page_addr(pool, page);
391
392            pool->stats[slot].used++;
393
394            goto done;
395        }
396    }
397
398    p = 0;
399
400    pool->stats[slot].fails++;
401
402done:
403
404    ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
405                   "slab alloc: %p", (void *) p);
406
407    return (void *) p;
408}
409
410
411void *
412ngx_slab_calloc(ngx_slab_pool_t *pool, size_t size)
413{
414    void  *p;
415
416    ngx_shmtx_lock(&pool->mutex);
417
418    p = ngx_slab_calloc_locked(pool, size);
419
420    ngx_shmtx_unlock(&pool->mutex);
421
422    return p;
423}
424
425
426void *
427ngx_slab_calloc_locked(ngx_slab_pool_t *pool, size_t size)
428{
429    void  *p;
430
431    p = ngx_slab_alloc_locked(pool, size);
432    if (p) {
433        ngx_memzero(p, size);
434    }
435
436    return p;
437}
438
439
440void
441ngx_slab_free(ngx_slab_pool_t *pool, void *p)
442{
443    ngx_shmtx_lock(&pool->mutex);
444
445    ngx_slab_free_locked(pool, p);
446
447    ngx_shmtx_unlock(&pool->mutex);
448}
449
450
451void
452ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p)
453{
454    size_t            size;
455    uintptr_t         slab, m, *bitmap;
456    ngx_uint_t        i, n, type, slot, shift, map;
457    ngx_slab_page_t  *slots, *page;
458
459    ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);
460
461    if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
462        ngx_slab_error(pool, NGX_LOG_ALERT, "ngx_slab_free(): outside of pool");
463        goto fail;
464    }
465
466    n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
467    page = &pool->pages[n];
468    slab = page->slab;
469    type = ngx_slab_page_type(page);
470
471    switch (type) {
472
473    case NGX_SLAB_SMALL:
474
475        shift = slab & NGX_SLAB_SHIFT_MASK;
476        size = (size_t) 1 << shift;
477
478        if ((uintptr_t) p & (size - 1)) {
479            goto wrong_chunk;
480        }
481
482        n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
483        m = (uintptr_t) 1 << (n % (sizeof(uintptr_t) * 8));
484        n /= sizeof(uintptr_t) * 8;
485        bitmap = (uintptr_t *)
486                             ((uintptr_t) p & ~((uintptr_t) ngx_pagesize - 1));
487
488        if (bitmap[n] & m) {
489            slot = shift - pool->min_shift;
490
491            if (page->next == NULL) {
492                slots = ngx_slab_slots(pool);
493
494                page->next = slots[slot].next;
495                slots[slot].next = page;
496
497                page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
498                page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
499            }
500
501            bitmap[n] &= ~m;
502
503            n = (ngx_pagesize >> shift) / ((1 << shift) * 8);
504
505            if (n == 0) {
506                n = 1;
507            }
508
509            if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
510                goto done;
511            }
512
513            map = (ngx_pagesize >> shift) / (sizeof(uintptr_t) * 8);
514
515            for (i = 1; i < map; i++) {
516                if (bitmap[i]) {
517                    goto done;
518                }
519            }
520
521            ngx_slab_free_pages(pool, page, 1);
522
523            pool->stats[slot].total -= (ngx_pagesize >> shift) - n;
524
525            goto done;
526        }
527
528        goto chunk_already_free;
529
530    case NGX_SLAB_EXACT:
531
532        m = (uintptr_t) 1 <<
533                (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
534        size = ngx_slab_exact_size;
535
536        if ((uintptr_t) p & (size - 1)) {
537            goto wrong_chunk;
538        }
539
540        if (slab & m) {
541            slot = ngx_slab_exact_shift - pool->min_shift;
542
543            if (slab == NGX_SLAB_BUSY) {
544                slots = ngx_slab_slots(pool);
545
546                page->next = slots[slot].next;
547                slots[slot].next = page;
548
549                page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
550                page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
551            }
552
553            page->slab &= ~m;
554
555            if (page->slab) {
556                goto done;
557            }
558
559            ngx_slab_free_pages(pool, page, 1);
560
561            pool->stats[slot].total -= sizeof(uintptr_t) * 8;
562
563            goto done;
564        }
565
566        goto chunk_already_free;
567
568    case NGX_SLAB_BIG:
569
570        shift = slab & NGX_SLAB_SHIFT_MASK;
571        size = (size_t) 1 << shift;
572
573        if ((uintptr_t) p & (size - 1)) {
574            goto wrong_chunk;
575        }
576
577        m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
578                              + NGX_SLAB_MAP_SHIFT);
579
580        if (slab & m) {
581            slot = shift - pool->min_shift;
582
583            if (page->next == NULL) {
584                slots = ngx_slab_slots(pool);
585
586                page->next = slots[slot].next;
587                slots[slot].next = page;
588
589                page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
590                page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
591            }
592
593            page->slab &= ~m;
594
595            if (page->slab & NGX_SLAB_MAP_MASK) {
596                goto done;
597            }
598
599            ngx_slab_free_pages(pool, page, 1);
600
601            pool->stats[slot].total -= ngx_pagesize >> shift;
602
603            goto done;
604        }
605
606        goto chunk_already_free;
607
608    case NGX_SLAB_PAGE:
609
610        if ((uintptr_t) p & (ngx_pagesize - 1)) {
611            goto wrong_chunk;
612        }
613
614        if (!(slab & NGX_SLAB_PAGE_START)) {
615            ngx_slab_error(pool, NGX_LOG_ALERT,
616                           "ngx_slab_free(): page is already free");
617            goto fail;
618        }
619
620        if (slab == NGX_SLAB_PAGE_BUSY) {
621            ngx_slab_error(pool, NGX_LOG_ALERT,
622                           "ngx_slab_free(): pointer to wrong page");
623            goto fail;
624        }
625
626        n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
627        size = slab & ~NGX_SLAB_PAGE_START;
628
629        ngx_slab_free_pages(pool, &pool->pages[n], size);
630
631        ngx_slab_junk(p, size << ngx_pagesize_shift);
632
633        return;
634    }
635
636    /* not reached */
637
638    return;
639
640done:
641
642    pool->stats[slot].used--;
643
644    ngx_slab_junk(p, size);
645
646    return;
647
648wrong_chunk:
649
650    ngx_slab_error(pool, NGX_LOG_ALERT,
651                   "ngx_slab_free(): pointer to wrong chunk");
652
653    goto fail;
654
655chunk_already_free:
656
657    ngx_slab_error(pool, NGX_LOG_ALERT,
658                   "ngx_slab_free(): chunk is already free");
659
660fail:
661
662    return;
663}
664
665
666static ngx_slab_page_t *
667ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
668{
669    ngx_slab_page_t  *page, *p;
670
671    for (page = pool->free.next; page != &pool->free; page = page->next) {
672
673        if (page->slab >= pages) {
674
675            if (page->slab > pages) {
676                page[page->slab - 1].prev = (uintptr_t) &page[pages];
677
678                page[pages].slab = page->slab - pages;
679                page[pages].next = page->next;
680                page[pages].prev = page->prev;
681
682                p = (ngx_slab_page_t *) page->prev;
683                p->next = &page[pages];
684                page->next->prev = (uintptr_t) &page[pages];
685
686            } else {
687                p = (ngx_slab_page_t *) page->prev;
688                p->next = page->next;
689                page->next->prev = page->prev;
690            }
691
692            page->slab = pages | NGX_SLAB_PAGE_START;
693            page->next = NULL;
694            page->prev = NGX_SLAB_PAGE;
695
696            pool->pfree -= pages;
697
698            if (--pages == 0) {
699                return page;
700            }
701
702            for (p = page + 1; pages; pages--) {
703                p->slab = NGX_SLAB_PAGE_BUSY;
704                p->next = NULL;
705                p->prev = NGX_SLAB_PAGE;
706                p++;
707            }
708
709            return page;
710        }
711    }
712
713    if (pool->log_nomem) {
714        ngx_slab_error(pool, NGX_LOG_CRIT,
715                       "ngx_slab_alloc() failed: no memory");
716    }
717
718    return NULL;
719}
720
721
722static void
723ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
724    ngx_uint_t pages)
725{
726    ngx_slab_page_t  *prev, *join;
727
728    pool->pfree += pages;
729
730    page->slab = pages--;
731
732    if (pages) {
733        ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
734    }
735
736    if (page->next) {
737        prev = ngx_slab_page_prev(page);
738        prev->next = page->next;
739        page->next->prev = page->prev;
740    }
741
742    join = page + page->slab;
743
744    if (join < pool->last) {
745
746        if (ngx_slab_page_type(join) == NGX_SLAB_PAGE) {
747
748            if (join->next != NULL) {
749                pages += join->slab;
750                page->slab += join->slab;
751
752                prev = ngx_slab_page_prev(join);
753                prev->next = join->next;
754                join->next->prev = join->prev;
755
756                join->slab = NGX_SLAB_PAGE_FREE;
757                join->next = NULL;
758                join->prev = NGX_SLAB_PAGE;
759            }
760        }
761    }
762
763    if (page > pool->pages) {
764        join = page - 1;
765
766        if (ngx_slab_page_type(join) == NGX_SLAB_PAGE) {
767
768            if (join->slab == NGX_SLAB_PAGE_FREE) {
769                join = ngx_slab_page_prev(join);
770            }
771
772            if (join->next != NULL) {
773                pages += join->slab;
774                join->slab += page->slab;
775
776                prev = ngx_slab_page_prev(join);
777                prev->next = join->next;
778                join->next->prev = join->prev;
779
780                page->slab = NGX_SLAB_PAGE_FREE;
781                page->next = NULL;
782                page->prev = NGX_SLAB_PAGE;
783
784                page = join;
785            }
786        }
787    }
788
789    if (pages) {
790        page[pages].prev = (uintptr_t) page;
791    }
792
793    page->prev = (uintptr_t) &pool->free;
794    page->next = pool->free.next;
795
796    page->next->prev = (uintptr_t) page;
797
798    pool->free.next = page;
799}
800
801
802static void
803ngx_slab_error(ngx_slab_pool_t *pool, ngx_uint_t level, char *text)
804{
805    ngx_log_error(level, ngx_cycle->log, 0, "%s%s", text, pool->log_ctx);
806}
807