1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) NGINX, Inc.
5 */
6
7 #include <nxt_main.h>
8
9
10 #define NXT_MEM_ZONE_PAGE_FREE 0
11 /*
12 * A page was never allocated before so it should be filled with
13 * junk on the first time allocation if memory debugging is enabled.
14 */
15 #define NXT_MEM_ZONE_PAGE_FRESH 1
16
17 /* An entire page is currently used, no chunks inside the page. */
18 #define NXT_MEM_ZONE_PAGE_USED 2
19
20
21 typedef struct nxt_mem_zone_page_s nxt_mem_zone_page_t;
22
23 struct nxt_mem_zone_page_s {
24 /*
25 * A size of page chunks if value is greater than or equal to 16.
26 * Otherwise it is used to mark page state: NXT_MEM_ZONE_PAGE_FREE,
27 * NXT_MEM_ZONE_PAGE_FRESH, and NXT_MEM_ZONE_PAGE_USED.
28 */
29 uint16_t size;
30
31 /* A number of free chunks of a chunked page. */
32 uint16_t chunks;
33
34 union {
35 /* A chunk bitmap if a number of chunks is lesser than 32. */
36 uint8_t map[4];
37 /*
38 * The count is a number of successive occupied pages in the first
39 * page. In the next occupied pages and in all free pages the count
40 * is zero, because a number of successive free pages is stored in
41 * free block size resided in beginning of the first free page.
42 */
43 uint32_t count;
44 } u;
45
46 /* Used for slot list of pages with free chunks. */
47 nxt_mem_zone_page_t *next;
48
49 /*
50 * Used to link of all pages including free, chunked and occupied
51 * pages to coalesce free pages.
52 */
53 nxt_queue_link_t link;
54 };
55
56
57 typedef struct {
58 uint32_t size;
59 uint32_t chunks;
60 uint32_t start;
61 uint32_t map_size;
62 nxt_mem_zone_page_t *pages;
63 } nxt_mem_zone_slot_t;
64
65
66 typedef struct {
67 NXT_RBTREE_NODE (node);
68 uint32_t size;
69 } nxt_mem_zone_free_block_t;
70
71
72 struct nxt_mem_zone_s {
73 nxt_thread_spinlock_t lock;
74 nxt_mem_zone_page_t *pages;
75 nxt_mem_zone_page_t sentinel_page;
76 nxt_rbtree_t free_pages;
77
78 uint32_t page_size_shift;
79 uint32_t page_size_mask;
80 uint32_t max_chunk_size;
81 uint32_t small_bitmap_min_size;
82
83 u_char *start;
84 u_char *end;
85
86 nxt_mem_zone_slot_t slots[];
87 };
88
89
90 #define nxt_mem_zone_page_addr(zone, page) \
91 (void *) (zone->start + ((page - zone->pages) << zone->page_size_shift))
92
93
94 #define nxt_mem_zone_addr_page(zone, addr) \
95 &zone->pages[((u_char *) addr - zone->start) >> zone->page_size_shift]
96
97
98 #define nxt_mem_zone_page_is_free(page) \
99 (page->size < NXT_MEM_ZONE_PAGE_USED)
100
101
102 #define nxt_mem_zone_page_is_chunked(page) \
103 (page->size >= 16)
104
105
106 #define nxt_mem_zone_page_bitmap(zone, slot) \
107 (slot->size < zone->small_bitmap_min_size)
108
109
110 #define nxt_mem_zone_set_chunk_free(map, chunk) \
111 map[chunk / 8] &= ~(0x80 >> (chunk & 7))
112
113
114 #define nxt_mem_zone_chunk_is_free(map, chunk) \
115 ((map[chunk / 8] & (0x80 >> (chunk & 7))) == 0)
116
117
118 #define nxt_mem_zone_fresh_junk(p, size) \
119 nxt_memset((p), 0xA5, size)
120
121
122 #define nxt_mem_zone_free_junk(p, size) \
123 nxt_memset((p), 0x5A, size)
124
125
126 static uint32_t nxt_mem_zone_pages(u_char *start, size_t zone_size,
127 nxt_uint_t page_size);
128 static void *nxt_mem_zone_slots_init(nxt_mem_zone_t *zone,
129 nxt_uint_t page_size);
130 static void nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot,
131 nxt_uint_t page_size);
132 static intptr_t nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1,
133 nxt_rbtree_node_t *node2);
134 static void *nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone,
135 nxt_mem_zone_slot_t *slot, size_t size);
136 static nxt_uint_t nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset,
137 nxt_uint_t size);
138 static void *nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment,
139 size_t size);
140 static nxt_mem_zone_page_t *nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone,
141 size_t alignment, uint32_t pages);
142 static nxt_mem_zone_free_block_t *
143 nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
144 uint32_t alignment, uint32_t pages);
145 static const char *nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone,
146 nxt_mem_zone_page_t *page, void *p);
147 static void nxt_mem_zone_free_pages(nxt_mem_zone_t *zone,
148 nxt_mem_zone_page_t *page, nxt_uint_t count);
149
150
151 static nxt_log_moderation_t nxt_mem_zone_log_moderation = {
152 NXT_LOG_ALERT, 2, "mem_zone_alloc() failed, not enough memory",
153 NXT_LOG_MODERATION
154 };
155
156
157 nxt_mem_zone_t *
nxt_mem_zone_init(u_char * start,size_t zone_size,nxt_uint_t page_size)158 nxt_mem_zone_init(u_char *start, size_t zone_size, nxt_uint_t page_size)
159 {
160 uint32_t pages;
161 nxt_uint_t n;
162 nxt_mem_zone_t *zone;
163 nxt_mem_zone_page_t *page;
164 nxt_mem_zone_free_block_t *block;
165
166 if (nxt_slow_path((page_size & (page_size - 1)) != 0)) {
167 nxt_thread_log_alert("mem zone page size must be a power of 2");
168 return NULL;
169 }
170
171 pages = nxt_mem_zone_pages(start, zone_size, page_size);
172 if (pages == 0) {
173 return NULL;
174 }
175
176 zone = (nxt_mem_zone_t *) start;
177
178 /* The function returns address after all slots. */
179 page = nxt_mem_zone_slots_init(zone, page_size);
180
181 zone->pages = page;
182
183 for (n = 0; n < pages; n++) {
184 page[n].size = NXT_MEM_ZONE_PAGE_FRESH;
185 }
186
187 /*
188 * A special sentinel page entry marked as used does not correspond
189 * to a real page. The entry simplifies neighbour queue nodes check
190 * in nxt_mem_zone_free_pages().
191 */
192 zone->sentinel_page.size = NXT_MEM_ZONE_PAGE_USED;
193 nxt_queue_sentinel(&zone->sentinel_page.link);
194 nxt_queue_insert_after(&zone->sentinel_page.link, &page->link);
195
196 /* rbtree of free pages. */
197
198 nxt_rbtree_init(&zone->free_pages, nxt_mem_zone_rbtree_compare);
199
200 block = (nxt_mem_zone_free_block_t *) zone->start;
201 block->size = pages;
202
203 nxt_rbtree_insert(&zone->free_pages, &block->node);
204
205 return zone;
206 }
207
208
209 static uint32_t
nxt_mem_zone_pages(u_char * start,size_t zone_size,nxt_uint_t page_size)210 nxt_mem_zone_pages(u_char *start, size_t zone_size, nxt_uint_t page_size)
211 {
212 u_char *end;
213 size_t reserved;
214 nxt_uint_t n, pages, size, chunks, last;
215 nxt_mem_zone_t *zone;
216
217 /*
218 * Find all maximum chunk sizes which zone page can be split on
219 * with minimum 16-byte step.
220 */
221 last = page_size / 16;
222 n = 0;
223 size = 32;
224
225 do {
226 chunks = page_size / size;
227
228 if (last != chunks) {
229 last = chunks;
230 n++;
231 }
232
233 size += 16;
234
235 } while (chunks > 1);
236
237 /*
238 * Find number of usable zone pages except zone bookkeeping data,
239 * slots, and pages entries.
240 */
241 reserved = sizeof(nxt_mem_zone_t) + (n * sizeof(nxt_mem_zone_slot_t));
242
243 end = nxt_trunc_ptr(start + zone_size, page_size);
244 zone_size = end - start;
245
246 pages = (zone_size - reserved) / (page_size + sizeof(nxt_mem_zone_page_t));
247
248 if (reserved > zone_size || pages == 0) {
249 nxt_thread_log_alert("mem zone size is too small: %uz", zone_size);
250 return 0;
251 }
252
253 reserved += pages * sizeof(nxt_mem_zone_page_t);
254 nxt_memzero(start, reserved);
255
256 zone = (nxt_mem_zone_t *) start;
257
258 zone->start = nxt_align_ptr(start + reserved, page_size);
259 zone->end = end;
260
261 nxt_thread_log_debug("mem zone pages: %uD, unused:%z", pages,
262 end - (zone->start + pages * page_size));
263
264 /*
265 * If a chunk size is lesser than zone->small_bitmap_min_size
266 * bytes, a page's chunk bitmap is larger than 32 bits and the
267 * bimap is placed at the start of the page.
268 */
269 zone->small_bitmap_min_size = page_size / 32;
270
271 zone->page_size_mask = page_size - 1;
272 zone->max_chunk_size = page_size / 2;
273
274 n = zone->max_chunk_size;
275
276 do {
277 zone->page_size_shift++;
278 n /= 2;
279 } while (n != 0);
280
281 return (uint32_t) pages;
282 }
283
284
285 static void *
nxt_mem_zone_slots_init(nxt_mem_zone_t * zone,nxt_uint_t page_size)286 nxt_mem_zone_slots_init(nxt_mem_zone_t *zone, nxt_uint_t page_size)
287 {
288 nxt_uint_t n, size, chunks;
289 nxt_mem_zone_slot_t *slot;
290
291 slot = zone->slots;
292
293 slot[0].chunks = page_size / 16;
294 slot[0].size = 16;
295
296 n = 0;
297 size = 32;
298
299 for ( ;; ) {
300 chunks = page_size / size;
301
302 if (slot[n].chunks != chunks) {
303
304 nxt_mem_zone_slot_init(&slot[n], page_size);
305
306 nxt_thread_log_debug(
307 "mem zone size:%uD chunks:%uD start:%uD map:%uD",
308 slot[n].size, slot[n].chunks + 1,
309 slot[n].start, slot[n].map_size);
310
311 n++;
312
313 if (chunks == 1) {
314 return &slot[n];
315 }
316 }
317
318 slot[n].chunks = chunks;
319 slot[n].size = size;
320 size += 16;
321 }
322 }
323
324
325 static void
nxt_mem_zone_slot_init(nxt_mem_zone_slot_t * slot,nxt_uint_t page_size)326 nxt_mem_zone_slot_init(nxt_mem_zone_slot_t *slot, nxt_uint_t page_size)
327 {
328 /*
329 * Calculate number of bytes required to store a chunk bitmap
330 * and align it to 4 bytes.
331 */
332 slot->map_size = nxt_align_size(((slot->chunks + 7) / 8), 4);
333
334 /* If chunk size is not a multiple of zone page size, there
335 * is surplus space which can be used for the chunk's bitmap.
336 */
337 slot->start = page_size - slot->chunks * slot->size;
338
339 /* slot->chunks should be one less than actual number of chunks. */
340 slot->chunks--;
341
342 if (slot->map_size > 4) {
343 /* A page's chunks bitmap is placed at the start of the page. */
344
345 if (slot->start < slot->map_size) {
346 /*
347 * There is no surplus space or the space is too
348 * small for chunks bitmap, so use the first chunks.
349 */
350 if (slot->size < slot->map_size) {
351 /* The first chunks are occupied by bitmap. */
352 slot->chunks -= slot->map_size / slot->size;
353 slot->start = nxt_align_size(slot->map_size, 16);
354
355 } else {
356 /* The first chunk is occupied by bitmap. */
357 slot->chunks--;
358 slot->start = slot->size;
359 }
360 }
361 }
362 }
363
364
365 /*
366 * Round up to the next highest power of 2. The algorithm is
367 * described in "Bit Twiddling Hacks" by Sean Eron Anderson.
368 */
369
370 nxt_inline uint32_t
nxt_next_highest_power_of_two(uint32_t n)371 nxt_next_highest_power_of_two(uint32_t n)
372 {
373 n--;
374 n |= n >> 1;
375 n |= n >> 2;
376 n |= n >> 4;
377 n |= n >> 8;
378 n |= n >> 16;
379 n++;
380
381 return n;
382 }
383
384
385 static intptr_t
nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)386 nxt_mem_zone_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
387 {
388 u_char *start1, *end1, *start2, *end2;
389 uint32_t n, size, size1, size2;
390 nxt_mem_zone_free_block_t *block1, *block2;
391
392 block1 = (nxt_mem_zone_free_block_t *) node1;
393 block2 = (nxt_mem_zone_free_block_t *) node2;
394
395 size1 = block1->size;
396 size2 = block2->size;
397
398 /*
399 * This subtractions do not overflow if number of pages of a free
400 * block is below 2^31-1. This allows to use blocks up to 128G if
401 * a zone page size is just 64 bytes.
402 */
403 n = size1 - size2;
404
405 if (n != 0) {
406 return n;
407 }
408
409 /*
410 * Sort equally sized blocks by their capability to allocate memory with
411 * alignment equal to the size rounded the previous higest power of 2.
412 */
413
414 /* Round the size to the previous higest power of two. */
415 size = nxt_next_highest_power_of_two(size1) >> 1;
416
417 /* Align the blocks' start and end to the rounded size. */
418 start1 = nxt_align_ptr(block1, size);
419 end1 = nxt_trunc_ptr((u_char *) block1 + size1, size);
420
421 start2 = nxt_align_ptr(block2, size);
422 end2 = nxt_trunc_ptr((u_char *) block2 + size2, size);
423
424 return (end1 - start1) - (end2 - start2);
425 }
426
427
428 void *
nxt_mem_zone_zalloc(nxt_mem_zone_t * zone,size_t size)429 nxt_mem_zone_zalloc(nxt_mem_zone_t *zone, size_t size)
430 {
431 void *p;
432
433 p = nxt_mem_zone_align(zone, 1, size);
434
435 if (nxt_fast_path(p != NULL)) {
436 nxt_memzero(p, size);
437 }
438
439 return p;
440 }
441
442
443 void *
nxt_mem_zone_align(nxt_mem_zone_t * zone,size_t alignment,size_t size)444 nxt_mem_zone_align(nxt_mem_zone_t *zone, size_t alignment, size_t size)
445 {
446 void *p;
447 nxt_mem_zone_slot_t *slot;
448
449 if (nxt_slow_path((alignment - 1) & alignment) != 0) {
450 /* Alignment must be a power of 2. */
451 return NULL;
452 }
453
454 if (size <= zone->max_chunk_size && alignment <= zone->max_chunk_size) {
455 /* All chunks are aligned to 16. */
456
457 if (alignment > 16) {
458 /*
459 * Chunks which size is power of 2 are aligned to the size.
460 * So allocation size should be increased to the next highest
461 * power of two. This can waste memory, but a main consumer
462 * of aligned allocations is lvlhsh which anyway allocates
463 * memory with alignment equal to size.
464 */
465 size = nxt_next_highest_power_of_two(size);
466 size = nxt_max(size, alignment);
467 }
468
469 /*
470 * Find a zone slot with appropriate chunk size.
471 * This operation can be performed without holding lock.
472 */
473 for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
474
475 nxt_thread_log_debug("mem zone alloc: @%uz:%uz chunk:%uD",
476 alignment, size, slot->size);
477
478 nxt_thread_spin_lock(&zone->lock);
479
480 p = nxt_mem_zone_alloc_small(zone, slot, size);
481
482 } else {
483
484 nxt_thread_log_debug("mem zone alloc: @%uz:%uz", alignment, size);
485
486 nxt_thread_spin_lock(&zone->lock);
487
488 p = nxt_mem_zone_alloc_large(zone, alignment, size);
489 }
490
491 nxt_thread_spin_unlock(&zone->lock);
492
493 if (nxt_fast_path(p != NULL)) {
494 nxt_thread_log_debug("mem zone alloc: %p", p);
495
496 } else {
497 nxt_log_alert_moderate(&nxt_mem_zone_log_moderation, nxt_thread_log(),
498 "nxt_mem_zone_alloc(%uz, %uz) failed, not enough memory",
499 alignment, size);
500 }
501
502 return p;
503 }
504
505
506 static void *
nxt_mem_zone_alloc_small(nxt_mem_zone_t * zone,nxt_mem_zone_slot_t * slot,size_t size)507 nxt_mem_zone_alloc_small(nxt_mem_zone_t *zone, nxt_mem_zone_slot_t *slot,
508 size_t size)
509 {
510 u_char *p;
511 uint8_t *map;
512 nxt_mem_zone_page_t *page;
513
514 page = slot->pages;
515
516 if (nxt_fast_path(page != NULL)) {
517
518 p = nxt_mem_zone_page_addr(zone, page);
519
520 if (nxt_mem_zone_page_bitmap(zone, slot)) {
521 /* A page's chunks bitmap is placed at the start of the page. */
522 map = p;
523
524 } else {
525 map = page->u.map;
526 }
527
528 p += nxt_mem_zone_alloc_chunk(map, slot->start, slot->size);
529
530 page->chunks--;
531
532 if (page->chunks == 0) {
533 /*
534 * Remove full page from the zone slot list of pages with
535 * free chunks.
536 */
537 slot->pages = page->next;
538 #if (NXT_DEBUG)
539 page->next = NULL;
540 #endif
541 }
542
543 return p;
544 }
545
546 page = nxt_mem_zone_alloc_pages(zone, 1, 1);
547
548 if (nxt_fast_path(page != NULL)) {
549
550 slot->pages = page;
551
552 page->size = slot->size;
553 /* slot->chunks are already one less. */
554 page->chunks = slot->chunks;
555 page->u.count = 0;
556 page->next = NULL;
557
558 p = nxt_mem_zone_page_addr(zone, page);
559
560 if (nxt_mem_zone_page_bitmap(zone, slot)) {
561 /* A page's chunks bitmap is placed at the start of the page. */
562 map = p;
563 nxt_memzero(map, slot->map_size);
564
565 } else {
566 map = page->u.map;
567 }
568
569 /* Mark the first chunk as busy. */
570 map[0] = 0x80;
571
572 return p + slot->start;
573 }
574
575 return NULL;
576 }
577
578
579 static nxt_uint_t
nxt_mem_zone_alloc_chunk(uint8_t * map,nxt_uint_t offset,nxt_uint_t size)580 nxt_mem_zone_alloc_chunk(uint8_t *map, nxt_uint_t offset, nxt_uint_t size)
581 {
582 uint8_t mask;
583 nxt_uint_t n;
584
585 n = 0;
586
587 /* The page must have at least one free chunk. */
588
589 for ( ;; ) {
590 /* The bitmap is always aligned to uint32_t. */
591
592 if (*(uint32_t *) &map[n] != 0xFFFFFFFF) {
593
594 do {
595 if (map[n] != 0xFF) {
596
597 mask = 0x80;
598
599 do {
600 if ((map[n] & mask) == 0) {
601 /* The free chunk is found. */
602 map[n] |= mask;
603 return offset;
604 }
605
606 offset += size;
607 mask >>= 1;
608
609 } while (mask != 0);
610
611 } else {
612 /* Fast-forward: all 8 chunks are occupied. */
613 offset += size * 8;
614 }
615
616 n++;
617
618 } while (n % 4 != 0);
619
620 } else {
621 /* Fast-forward: all 32 chunks are occupied. */
622 offset += size * 32;
623 n += 4;
624 }
625 }
626 }
627
628
629 static void *
nxt_mem_zone_alloc_large(nxt_mem_zone_t * zone,size_t alignment,size_t size)630 nxt_mem_zone_alloc_large(nxt_mem_zone_t *zone, size_t alignment, size_t size)
631 {
632 uint32_t pages;
633 nxt_mem_zone_page_t *page;
634
635 pages = (size + zone->page_size_mask) >> zone->page_size_shift;
636
637 page = nxt_mem_zone_alloc_pages(zone, alignment, pages);
638
639 if (nxt_fast_path(page != NULL)) {
640 return nxt_mem_zone_page_addr(zone, page);
641 }
642
643 return NULL;
644 }
645
646
647 static nxt_mem_zone_page_t *
nxt_mem_zone_alloc_pages(nxt_mem_zone_t * zone,size_t alignment,uint32_t pages)648 nxt_mem_zone_alloc_pages(nxt_mem_zone_t *zone, size_t alignment, uint32_t pages)
649 {
650 u_char *p;
651 size_t prev_size;
652 uint32_t prev_pages, node_pages, next_pages;
653 nxt_uint_t n;
654 nxt_mem_zone_page_t *prev_page, *page, *next_page;
655 nxt_mem_zone_free_block_t *block, *next_block;
656
657 block = nxt_mem_zone_find_free_block(zone,
658 nxt_rbtree_root(&zone->free_pages),
659 alignment, pages);
660
661 if (nxt_slow_path(block == NULL)) {
662 return NULL;
663 }
664
665 node_pages = block->size;
666
667 nxt_rbtree_delete(&zone->free_pages, &block->node);
668
669 p = nxt_align_ptr(block, alignment);
670 page = nxt_mem_zone_addr_page(zone, p);
671
672 prev_size = p - (u_char *) block;
673
674 if (prev_size != 0) {
675 prev_pages = prev_size >> zone->page_size_shift;
676 node_pages -= prev_pages;
677
678 block->size = prev_pages;
679 nxt_rbtree_insert(&zone->free_pages, &block->node);
680
681 prev_page = nxt_mem_zone_addr_page(zone, block);
682 nxt_queue_insert_after(&prev_page->link, &page->link);
683 }
684
685 next_pages = node_pages - pages;
686
687 if (next_pages != 0) {
688 next_page = &page[pages];
689 next_block = nxt_mem_zone_page_addr(zone, next_page);
690 next_block->size = next_pages;
691
692 nxt_rbtree_insert(&zone->free_pages, &next_block->node);
693 nxt_queue_insert_after(&page->link, &next_page->link);
694 }
695
696 /* Go through pages after all rbtree operations to not trash CPU cache. */
697
698 page[0].u.count = pages;
699
700 for (n = 0; n < pages; n++) {
701
702 if (page[n].size == NXT_MEM_ZONE_PAGE_FRESH) {
703 nxt_mem_zone_fresh_junk(nxt_mem_zone_page_addr(zone, &page[n]),
704 zone->page_size_mask + 1);
705 }
706
707 page[n].size = NXT_MEM_ZONE_PAGE_USED;
708 }
709
710 return page;
711 }
712
713
714 /*
715 * Free blocks are sorted by size and then if the sizes are equal
716 * by aligned allocation capabilty. The former criterion is just
717 * comparison with a requested size and it can be used for iteractive
718 * search. The later criterion cannot be tested only by the requested
719 * size and alignment, so recursive in-order tree traversal is required
720 * to find a suitable free block. nxt_mem_zone_find_free_block() uses
721 * only recursive in-order tree traversal because anyway the slowest part
722 * of the algorithm are CPU cache misses. Besides the last tail recursive
723 * call may be optimized by compiler into iteractive search.
724 */
725
726 static nxt_mem_zone_free_block_t *
nxt_mem_zone_find_free_block(nxt_mem_zone_t * zone,nxt_rbtree_node_t * node,uint32_t alignment,uint32_t pages)727 nxt_mem_zone_find_free_block(nxt_mem_zone_t *zone, nxt_rbtree_node_t *node,
728 uint32_t alignment, uint32_t pages)
729 {
730 u_char *aligned, *end;
731 nxt_mem_zone_free_block_t *block, *free_block;
732
733 if (node == nxt_rbtree_sentinel(&zone->free_pages)) {
734 return NULL;
735 }
736
737 block = (nxt_mem_zone_free_block_t *) node;
738
739 if (pages <= block->size) {
740
741 free_block = nxt_mem_zone_find_free_block(zone, block->node.left,
742 alignment, pages);
743 if (free_block != NULL) {
744 return free_block;
745 }
746
747 aligned = nxt_align_ptr(block, alignment);
748
749 if (pages == block->size) {
750 if (aligned == (u_char *) block) {
751 /* Exact match. */
752 return block;
753 }
754
755 } else { /* pages < block->size */
756 aligned += pages << zone->page_size_shift;
757 end = nxt_pointer_to(block, block->size << zone->page_size_shift);
758
759 if (aligned <= end) {
760 return block;
761 }
762 }
763 }
764
765 return nxt_mem_zone_find_free_block(zone, block->node.right,
766 alignment, pages);
767 }
768
769
770 void
nxt_mem_zone_free(nxt_mem_zone_t * zone,void * p)771 nxt_mem_zone_free(nxt_mem_zone_t *zone, void *p)
772 {
773 nxt_uint_t count;
774 const char *err;
775 nxt_mem_zone_page_t *page;
776
777 nxt_thread_log_debug("mem zone free: %p", p);
778
779 if (nxt_fast_path(zone->start <= (u_char *) p
780 && (u_char *) p < zone->end))
781 {
782 page = nxt_mem_zone_addr_page(zone, p);
783
784 nxt_thread_spin_lock(&zone->lock);
785
786 if (nxt_mem_zone_page_is_chunked(page)) {
787 err = nxt_mem_zone_free_chunk(zone, page, p);
788
789 } else if (nxt_slow_path(nxt_mem_zone_page_is_free(page))) {
790 err = "page is already free";
791
792 } else if (nxt_slow_path((uintptr_t) p & zone->page_size_mask) != 0) {
793 err = "invalid pointer to chunk";
794
795 } else {
796 count = page->u.count;
797
798 if (nxt_fast_path(count != 0)) {
799 nxt_mem_zone_free_junk(p, count * zone->page_size_mask + 1);
800 nxt_mem_zone_free_pages(zone, page, count);
801 err = NULL;
802
803 } else {
804 /* Not the first allocated page. */
805 err = "pointer to wrong page";
806 }
807 }
808
809 nxt_thread_spin_unlock(&zone->lock);
810
811 } else {
812 err = "pointer is out of zone";
813 }
814
815 if (nxt_slow_path(err != NULL)) {
816 nxt_thread_log_alert("nxt_mem_zone_free(%p): %s", p, err);
817 }
818 }
819
820
821 static const char *
nxt_mem_zone_free_chunk(nxt_mem_zone_t * zone,nxt_mem_zone_page_t * page,void * p)822 nxt_mem_zone_free_chunk(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
823 void *p)
824 {
825 u_char *map;
826 uint32_t size, offset, chunk;
827 nxt_mem_zone_page_t *pg, **ppg;
828 nxt_mem_zone_slot_t *slot;
829
830 size = page->size;
831
832 /* Find a zone slot with appropriate chunk size. */
833 for (slot = zone->slots; slot->size < size; slot++) { /* void */ }
834
835 offset = (uintptr_t) p & zone->page_size_mask;
836 offset -= slot->start;
837
838 chunk = offset / size;
839
840 if (nxt_slow_path(offset != chunk * size)) {
841 return "pointer to wrong chunk";
842 }
843
844 if (nxt_mem_zone_page_bitmap(zone, slot)) {
845 /* A page's chunks bitmap is placed at the start of the page. */
846 map = (u_char *) ((uintptr_t) p & ~((uintptr_t) zone->page_size_mask));
847
848 } else {
849 map = page->u.map;
850 }
851
852 if (nxt_mem_zone_chunk_is_free(map, chunk)) {
853 return "chunk is already free";
854 }
855
856 nxt_mem_zone_set_chunk_free(map, chunk);
857
858 nxt_mem_zone_free_junk(p, page->size);
859
860 if (page->chunks == 0) {
861 page->chunks = 1;
862
863 /* Add the page to the head of slot list of pages with free chunks. */
864 page->next = slot->pages;
865 slot->pages = page;
866
867 } else if (page->chunks != slot->chunks) {
868 page->chunks++;
869
870 } else {
871
872 if (map != page->u.map) {
873 nxt_mem_zone_free_junk(map, slot->map_size);
874 }
875
876 /*
877 * All chunks are free, remove the page from the slot list of pages
878 * with free chunks and add the page to the free pages tree.
879 */
880 ppg = &slot->pages;
881
882 for (pg = slot->pages; pg != NULL; pg = pg->next) {
883
884 if (pg == page) {
885 *ppg = page->next;
886 break;
887 }
888
889 ppg = &pg->next;
890 }
891
892 nxt_mem_zone_free_pages(zone, page, 1);
893 }
894
895 return NULL;
896 }
897
898
899 static void
nxt_mem_zone_free_pages(nxt_mem_zone_t * zone,nxt_mem_zone_page_t * page,nxt_uint_t count)900 nxt_mem_zone_free_pages(nxt_mem_zone_t *zone, nxt_mem_zone_page_t *page,
901 nxt_uint_t count)
902 {
903 nxt_mem_zone_page_t *prev_page, *next_page;
904 nxt_mem_zone_free_block_t *block, *prev_block, *next_block;
905
906 page->size = NXT_MEM_ZONE_PAGE_FREE;
907 page->chunks = 0;
908 page->u.count = 0;
909 page->next = NULL;
910
911 nxt_memzero(&page[1], (count - 1) * sizeof(nxt_mem_zone_page_t));
912
913 next_page = nxt_queue_link_data(page->link.next, nxt_mem_zone_page_t, link);
914
915 if (nxt_mem_zone_page_is_free(next_page)) {
916
917 /* Coalesce with the next free pages. */
918
919 nxt_queue_remove(&next_page->link);
920 nxt_memzero(next_page, sizeof(nxt_mem_zone_page_t));
921
922 next_block = nxt_mem_zone_page_addr(zone, next_page);
923 count += next_block->size;
924 nxt_rbtree_delete(&zone->free_pages, &next_block->node);
925 }
926
927 prev_page = nxt_queue_link_data(page->link.prev, nxt_mem_zone_page_t, link);
928
929 if (nxt_mem_zone_page_is_free(prev_page)) {
930
931 /* Coalesce with the previous free pages. */
932
933 nxt_queue_remove(&page->link);
934
935 prev_block = nxt_mem_zone_page_addr(zone, prev_page);
936 count += prev_block->size;
937 nxt_rbtree_delete(&zone->free_pages, &prev_block->node);
938
939 prev_block->size = count;
940 nxt_rbtree_insert(&zone->free_pages, &prev_block->node);
941
942 return;
943 }
944
945 block = nxt_mem_zone_page_addr(zone, page);
946 block->size = count;
947 nxt_rbtree_insert(&zone->free_pages, &block->node);
948 }
949