3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
7 #include <ngx_config.h>
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
17 #if (NGX_PTR_SIZE == 4)
19 #define NGX_SLAB_PAGE_FREE 0
20 #define NGX_SLAB_PAGE_BUSY 0xffffffff
21 #define NGX_SLAB_PAGE_START 0x80000000
23 #define NGX_SLAB_SHIFT_MASK 0x0000000f
24 #define NGX_SLAB_MAP_MASK 0xffff0000
25 #define NGX_SLAB_MAP_SHIFT 16
27 #define NGX_SLAB_BUSY 0xffffffff
29 #else /* (NGX_PTR_SIZE == 8) */
31 #define NGX_SLAB_PAGE_FREE 0
32 #define NGX_SLAB_PAGE_BUSY 0xffffffffffffffff
33 #define NGX_SLAB_PAGE_START 0x8000000000000000
35 #define NGX_SLAB_SHIFT_MASK 0x000000000000000f
36 #define NGX_SLAB_MAP_MASK 0xffffffff00000000
37 #define NGX_SLAB_MAP_SHIFT 32
39 #define NGX_SLAB_BUSY 0xffffffffffffffff
44 #if (NGX_DEBUG_MALLOC)
46 #define ngx_slab_junk(p, size) ngx_memset(p, 0xA5, size)
48 #elif (NGX_HAVE_DEBUG_MALLOC)
50 #define ngx_slab_junk(p, size) \
51 if (ngx_debug_malloc) ngx_memset(p, 0xA5, size)
55 #define ngx_slab_junk(p, size)
59 static ngx_slab_page_t
*ngx_slab_alloc_pages(ngx_slab_pool_t
*pool
,
61 static void ngx_slab_free_pages(ngx_slab_pool_t
*pool
, ngx_slab_page_t
*page
,
63 static void ngx_slab_error(ngx_slab_pool_t
*pool
, ngx_uint_t level
,
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
;
73 ngx_slab_init(ngx_slab_pool_t
*pool
)
78 ngx_uint_t i
, n
, pages
;
79 ngx_slab_page_t
*slots
;
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
++) {
91 pool
->min_size
= 1 << pool
->min_shift
;
93 p
= (u_char
*) pool
+ sizeof(ngx_slab_pool_t
);
96 ngx_slab_junk(p
, size
);
98 slots
= (ngx_slab_page_t
*) p
;
99 n
= ngx_pagesize_shift
- pool
->min_shift
;
101 for (i
= 0; i
< n
; i
++) {
103 slots
[i
].next
= &slots
[i
];
107 p
+= n
* sizeof(ngx_slab_page_t
);
109 pages
= (ngx_uint_t
) (size
/ (ngx_pagesize
+ sizeof(ngx_slab_page_t
)));
111 ngx_memzero(p
, pages
* sizeof(ngx_slab_page_t
));
113 pool
->pages
= (ngx_slab_page_t
*) p
;
116 pool
->free
.next
= (ngx_slab_page_t
*) p
;
118 pool
->pages
->slab
= pages
;
119 pool
->pages
->next
= &pool
->free
;
120 pool
->pages
->prev
= (uintptr_t) &pool
->free
;
122 pool
->start
= (u_char
*)
123 ngx_align_ptr((uintptr_t) p
+ pages
* sizeof(ngx_slab_page_t
),
126 m
= pages
- (pool
->end
- pool
->start
) / ngx_pagesize
;
129 pool
->pages
->slab
= pages
;
132 pool
->log_ctx
= &pool
->zero
;
138 ngx_slab_alloc(ngx_slab_pool_t
*pool
, size_t size
)
142 ngx_shmtx_lock(&pool
->mutex
);
144 p
= ngx_slab_alloc_locked(pool
, size
);
146 ngx_shmtx_unlock(&pool
->mutex
);
153 ngx_slab_alloc_locked(ngx_slab_pool_t
*pool
, size_t size
)
156 uintptr_t p
, n
, m
, mask
, *bitmap
;
157 ngx_uint_t i
, slot
, shift
, map
;
158 ngx_slab_page_t
*page
, *prev
, *slots
;
160 if (size
>= ngx_slab_max_size
) {
162 ngx_log_debug1(NGX_LOG_DEBUG_ALLOC
, ngx_cycle
->log
, 0,
163 "slab alloc: %uz", size
);
165 page
= ngx_slab_alloc_pages(pool
, (size
>> ngx_pagesize_shift
)
166 + ((size
% ngx_pagesize
) ? 1 : 0));
168 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
169 p
+= (uintptr_t) pool
->start
;
178 if (size
> pool
->min_size
) {
180 for (s
= size
- 1; s
>>= 1; shift
++) { /* void */ }
181 slot
= shift
- pool
->min_shift
;
184 size
= pool
->min_size
;
185 shift
= pool
->min_shift
;
189 ngx_log_debug2(NGX_LOG_DEBUG_ALLOC
, ngx_cycle
->log
, 0,
190 "slab alloc: %uz slot: %ui", size
, slot
);
192 slots
= (ngx_slab_page_t
*) ((u_char
*) pool
+ sizeof(ngx_slab_pool_t
));
193 page
= slots
[slot
].next
;
195 if (page
->next
!= page
) {
197 if (shift
< ngx_slab_exact_shift
) {
200 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
201 bitmap
= (uintptr_t *) (pool
->start
+ p
);
203 map
= (1 << (ngx_pagesize_shift
- shift
))
204 / (sizeof(uintptr_t) * 8);
206 for (n
= 0; n
< map
; n
++) {
208 if (bitmap
[n
] != NGX_SLAB_BUSY
) {
210 for (m
= 1, i
= 0; m
; m
<<= 1, i
++) {
211 if ((bitmap
[n
] & m
)) {
217 i
= ((n
* sizeof(uintptr_t) * 8) << shift
)
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
;
229 prev
= (ngx_slab_page_t
*)
230 (page
->prev
& ~NGX_SLAB_PAGE_MASK
);
231 prev
->next
= page
->next
;
232 page
->next
->prev
= page
->prev
;
235 page
->prev
= NGX_SLAB_SMALL
;
238 p
= (uintptr_t) bitmap
+ i
;
249 } else if (shift
== ngx_slab_exact_shift
) {
252 if (page
->slab
!= NGX_SLAB_BUSY
) {
254 for (m
= 1, i
= 0; m
; m
<<= 1, i
++) {
255 if ((page
->slab
& m
)) {
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
;
268 page
->prev
= NGX_SLAB_EXACT
;
271 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
273 p
+= (uintptr_t) pool
->start
;
283 } else { /* shift > ngx_slab_exact_shift */
285 n
= ngx_pagesize_shift
- (page
->slab
& NGX_SLAB_SHIFT_MASK
);
287 n
= ((uintptr_t) 1 << n
) - 1;
288 mask
= n
<< NGX_SLAB_MAP_SHIFT
;
291 if ((page
->slab
& NGX_SLAB_MAP_MASK
) != mask
) {
293 for (m
= (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT
, i
= 0;
297 if ((page
->slab
& m
)) {
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
;
310 page
->prev
= NGX_SLAB_BIG
;
313 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
315 p
+= (uintptr_t) pool
->start
;
327 page
= ngx_slab_alloc_pages(pool
, 1);
330 if (shift
< ngx_slab_exact_shift
) {
331 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
332 bitmap
= (uintptr_t *) (pool
->start
+ p
);
335 n
= (1 << (ngx_pagesize_shift
- shift
)) / 8 / s
;
341 bitmap
[0] = (2 << n
) - 1;
343 map
= (1 << (ngx_pagesize_shift
- shift
)) / (sizeof(uintptr_t) * 8);
345 for (i
= 1; i
< map
; i
++) {
350 page
->next
= &slots
[slot
];
351 page
->prev
= (uintptr_t) &slots
[slot
] | NGX_SLAB_SMALL
;
353 slots
[slot
].next
= page
;
355 p
= ((page
- pool
->pages
) << ngx_pagesize_shift
) + s
* n
;
356 p
+= (uintptr_t) pool
->start
;
360 } else if (shift
== ngx_slab_exact_shift
) {
363 page
->next
= &slots
[slot
];
364 page
->prev
= (uintptr_t) &slots
[slot
] | NGX_SLAB_EXACT
;
366 slots
[slot
].next
= page
;
368 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
369 p
+= (uintptr_t) pool
->start
;
373 } else { /* shift > ngx_slab_exact_shift */
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
;
379 slots
[slot
].next
= page
;
381 p
= (page
- pool
->pages
) << ngx_pagesize_shift
;
382 p
+= (uintptr_t) pool
->start
;
392 ngx_log_debug1(NGX_LOG_DEBUG_ALLOC
, ngx_cycle
->log
, 0, "slab alloc: %p", p
);
399 ngx_slab_free(ngx_slab_pool_t
*pool
, void *p
)
401 ngx_shmtx_lock(&pool
->mutex
);
403 ngx_slab_free_locked(pool
, p
);
405 ngx_shmtx_unlock(&pool
->mutex
);
410 ngx_slab_free_locked(ngx_slab_pool_t
*pool
, void *p
)
413 uintptr_t slab
, m
, *bitmap
;
414 ngx_uint_t n
, type
, slot
, shift
, map
;
415 ngx_slab_page_t
*slots
, *page
;
417 ngx_log_debug1(NGX_LOG_DEBUG_ALLOC
, ngx_cycle
->log
, 0, "slab free: %p", p
);
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");
424 n
= ((u_char
*) p
- pool
->start
) >> ngx_pagesize_shift
;
425 page
= &pool
->pages
[n
];
427 type
= page
->prev
& NGX_SLAB_PAGE_MASK
;
433 shift
= slab
& NGX_SLAB_SHIFT_MASK
;
436 if ((uintptr_t) p
& (size
- 1)) {
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));
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
;
452 page
->next
= slots
[slot
].next
;
453 slots
[slot
].next
= page
;
455 page
->prev
= (uintptr_t) &slots
[slot
] | NGX_SLAB_SMALL
;
456 page
->next
->prev
= (uintptr_t) page
| NGX_SLAB_SMALL
;
461 n
= (1 << (ngx_pagesize_shift
- shift
)) / 8 / (1 << shift
);
467 if (bitmap
[0] & ~(((uintptr_t) 1 << n
) - 1)) {
471 map
= (1 << (ngx_pagesize_shift
- shift
)) / (sizeof(uintptr_t) * 8);
473 for (n
= 1; n
< map
; n
++) {
479 ngx_slab_free_pages(pool
, page
, 1);
484 goto chunk_already_free
;
489 (((uintptr_t) p
& (ngx_pagesize
- 1)) >> ngx_slab_exact_shift
);
490 size
= ngx_slab_exact_size
;
492 if ((uintptr_t) p
& (size
- 1)) {
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
;
502 page
->next
= slots
[slot
].next
;
503 slots
[slot
].next
= page
;
505 page
->prev
= (uintptr_t) &slots
[slot
] | NGX_SLAB_EXACT
;
506 page
->next
->prev
= (uintptr_t) page
| NGX_SLAB_EXACT
;
515 ngx_slab_free_pages(pool
, page
, 1);
520 goto chunk_already_free
;
524 shift
= slab
& NGX_SLAB_SHIFT_MASK
;
527 if ((uintptr_t) p
& (size
- 1)) {
531 m
= (uintptr_t) 1 << ((((uintptr_t) p
& (ngx_pagesize
- 1)) >> shift
)
532 + NGX_SLAB_MAP_SHIFT
);
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
;
541 page
->next
= slots
[slot
].next
;
542 slots
[slot
].next
= page
;
544 page
->prev
= (uintptr_t) &slots
[slot
] | NGX_SLAB_BIG
;
545 page
->next
->prev
= (uintptr_t) page
| NGX_SLAB_BIG
;
550 if (page
->slab
& NGX_SLAB_MAP_MASK
) {
554 ngx_slab_free_pages(pool
, page
, 1);
559 goto chunk_already_free
;
563 if ((uintptr_t) p
& (ngx_pagesize
- 1)) {
567 if (slab
== NGX_SLAB_PAGE_FREE
) {
568 ngx_slab_error(pool
, NGX_LOG_ALERT
,
569 "ngx_slab_free(): page is already free");
573 if (slab
== NGX_SLAB_PAGE_BUSY
) {
574 ngx_slab_error(pool
, NGX_LOG_ALERT
,
575 "ngx_slab_free(): pointer to wrong page");
579 n
= ((u_char
*) p
- pool
->start
) >> ngx_pagesize_shift
;
580 size
= slab
& ~NGX_SLAB_PAGE_START
;
582 ngx_slab_free_pages(pool
, &pool
->pages
[n
], size
);
584 ngx_slab_junk(p
, size
<< ngx_pagesize_shift
);
595 ngx_slab_junk(p
, size
);
601 ngx_slab_error(pool
, NGX_LOG_ALERT
,
602 "ngx_slab_free(): pointer to wrong chunk");
608 ngx_slab_error(pool
, NGX_LOG_ALERT
,
609 "ngx_slab_free(): chunk is already free");
617 static ngx_slab_page_t
*
618 ngx_slab_alloc_pages(ngx_slab_pool_t
*pool
, ngx_uint_t pages
)
620 ngx_slab_page_t
*page
, *p
;
622 for (page
= pool
->free
.next
; page
!= &pool
->free
; page
= page
->next
) {
624 if (page
->slab
>= pages
) {
626 if (page
->slab
> pages
) {
627 page
[pages
].slab
= page
->slab
- pages
;
628 page
[pages
].next
= page
->next
;
629 page
[pages
].prev
= page
->prev
;
631 p
= (ngx_slab_page_t
*) page
->prev
;
632 p
->next
= &page
[pages
];
633 page
->next
->prev
= (uintptr_t) &page
[pages
];
636 p
= (ngx_slab_page_t
*) page
->prev
;
637 p
->next
= page
->next
;
638 page
->next
->prev
= page
->prev
;
641 page
->slab
= pages
| NGX_SLAB_PAGE_START
;
643 page
->prev
= NGX_SLAB_PAGE
;
649 for (p
= page
+ 1; pages
; pages
--) {
650 p
->slab
= NGX_SLAB_PAGE_BUSY
;
652 p
->prev
= NGX_SLAB_PAGE
;
660 ngx_slab_error(pool
, NGX_LOG_CRIT
, "ngx_slab_alloc() failed: no memory");
667 ngx_slab_free_pages(ngx_slab_pool_t
*pool
, ngx_slab_page_t
*page
,
670 ngx_slab_page_t
*prev
;
672 page
->slab
= pages
--;
675 ngx_memzero(&page
[1], pages
* sizeof(ngx_slab_page_t
));
679 prev
= (ngx_slab_page_t
*) (page
->prev
& ~NGX_SLAB_PAGE_MASK
);
680 prev
->next
= page
->next
;
681 page
->next
->prev
= page
->prev
;
684 page
->prev
= (uintptr_t) &pool
->free
;
685 page
->next
= pool
->free
.next
;
687 page
->next
->prev
= (uintptr_t) page
;
689 pool
->free
.next
= page
;
694 ngx_slab_error(ngx_slab_pool_t
*pool
, ngx_uint_t level
, char *text
)
696 ngx_log_error(level
, ngx_cycle
->log
, 0, "%s%s", text
, pool
->log_ctx
);