1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) NGINX, Inc.
5 */
6
7
8 #include <njs_main.h>
9
10
11 /*
12 * A memory cache pool allocates memory in clusters of specified size and
13 * aligned to page_alignment. A cluster is divided on pages of specified
14 * size. Page size must be a power of 2. A page can be used entirely or
15 * can be divided on chunks of equal size. Chunk size must be a power of 2.
16 * A cluster can contains pages with different chunk sizes. Cluster size
17 * must be a multiple of page size and may be not a power of 2. Allocations
18 * greater than page are allocated outside clusters. Start addresses and
19 * sizes of the clusters and large allocations are stored in rbtree blocks
20 * to find them on free operations. The rbtree nodes are sorted by start
21 * addresses.
22 */
23
24
25 typedef struct {
26 /*
27 * Used to link pages with free chunks in pool chunk slot list
28 * or to link free pages in clusters.
29 */
30 njs_queue_link_t link;
31
32 /*
33 * Size of chunks or page shifted by mp->chunk_size_shift.
34 * Zero means that page is free.
35 */
36 uint8_t size;
37
38 /*
39 * Page number in page cluster.
40 * There can be no more than 256 pages in a cluster.
41 */
42 uint8_t number;
43
44 /* Number of free chunks of a chunked page. */
45 uint8_t chunks;
46
47 uint8_t _unused;
48
49 /* Chunk bitmap. There can be no more than 32 chunks in a page. */
50 uint8_t map[4];
51 } njs_mp_page_t;
52
53
54 typedef enum {
55 /* Block of cluster. The block is allocated apart of the cluster. */
56 NJS_MP_CLUSTER_BLOCK = 0,
57 /*
58 * Block of large allocation.
59 * The block is allocated apart of the allocation.
60 */
61 NJS_MP_DISCRETE_BLOCK,
62 /*
63 * Block of large allocation.
64 * The block is allocated just after of the allocation.
65 */
66 NJS_MP_EMBEDDED_BLOCK,
67 } njs_mp_block_type_t;
68
69
70 typedef struct {
71 NJS_RBTREE_NODE (node);
72 njs_mp_block_type_t type:8;
73
74 /* Block size must be less than 4G. */
75 uint32_t size;
76
77 u_char *start;
78 njs_mp_page_t pages[];
79 } njs_mp_block_t;
80
81
82 typedef struct {
83 njs_queue_t pages;
84
85 /* Size of page chunks. */
86 #if (NJS_64BIT)
87 uint32_t size;
88 #else
89 uint16_t size;
90 #endif
91
92 /* Maximum number of free chunks in chunked page. */
93 uint8_t chunks;
94 } njs_mp_slot_t;
95
96
97 struct njs_mp_s {
98 /* rbtree of njs_mp_block_t. */
99 njs_rbtree_t blocks;
100
101 njs_queue_t free_pages;
102
103 uint8_t chunk_size_shift;
104 uint8_t page_size_shift;
105 uint32_t page_size;
106 uint32_t page_alignment;
107 uint32_t cluster_size;
108
109 njs_mp_cleanup_t *cleanup;
110
111 njs_mp_slot_t slots[];
112 };
113
114
115 #define njs_mp_chunk_is_free(map, chunk) \
116 ((map[chunk / 8] & (0x80 >> (chunk & 7))) == 0)
117
118
119 #define njs_mp_chunk_set_free(map, chunk) \
120 map[chunk / 8] &= ~(0x80 >> (chunk & 7))
121
122
123 #define njs_mp_free_junk(p, size) \
124 njs_memset((p), 0x5A, size)
125
126
127 #define njs_is_power_of_two(value) \
128 ((((value) - 1) & (value)) == 0)
129
130
131 static njs_uint_t njs_mp_shift(njs_uint_t n);
132 #if !(NJS_DEBUG_MEMORY)
133 static void *njs_mp_alloc_small(njs_mp_t *mp, size_t size);
134 static njs_uint_t njs_mp_alloc_chunk(u_char *map, njs_uint_t size);
135 static njs_mp_page_t *njs_mp_alloc_page(njs_mp_t *mp);
136 static njs_mp_block_t *njs_mp_alloc_cluster(njs_mp_t *mp);
137 #endif
138 static void *njs_mp_alloc_large(njs_mp_t *mp, size_t alignment, size_t size);
139 static intptr_t njs_mp_rbtree_compare(njs_rbtree_node_t *node1,
140 njs_rbtree_node_t *node2);
141 static njs_mp_block_t *njs_mp_find_block(njs_rbtree_t *tree,
142 u_char *p);
143 static const char *njs_mp_chunk_free(njs_mp_t *mp, njs_mp_block_t *cluster,
144 u_char *p);
145
146
147 njs_mp_t *
njs_mp_create(size_t cluster_size,size_t page_alignment,size_t page_size,size_t min_chunk_size)148 njs_mp_create(size_t cluster_size, size_t page_alignment, size_t page_size,
149 size_t min_chunk_size)
150 {
151 /* Alignment and sizes must be a power of 2. */
152
153 if (njs_slow_path(!njs_is_power_of_two(page_alignment)
154 || !njs_is_power_of_two(page_size)
155 || !njs_is_power_of_two(min_chunk_size)))
156 {
157 return NULL;
158 }
159
160 page_alignment = njs_max(page_alignment, NJS_MAX_ALIGNMENT);
161
162 if (njs_slow_path(page_size < 64
163 || page_size < page_alignment
164 || page_size < min_chunk_size
165 || min_chunk_size * 32 < page_size
166 || cluster_size < page_size
167 || cluster_size / page_size > 256
168 || cluster_size % page_size != 0))
169 {
170 return NULL;
171 }
172
173 return njs_mp_fast_create(cluster_size, page_alignment, page_size,
174 min_chunk_size);
175 }
176
177
178 njs_mp_t *
njs_mp_fast_create(size_t cluster_size,size_t page_alignment,size_t page_size,size_t min_chunk_size)179 njs_mp_fast_create(size_t cluster_size, size_t page_alignment, size_t page_size,
180 size_t min_chunk_size)
181 {
182 njs_mp_t *mp;
183 njs_uint_t slots, chunk_size;
184 njs_mp_slot_t *slot;
185
186 slots = 0;
187 chunk_size = page_size;
188
189 do {
190 slots++;
191 chunk_size /= 2;
192 } while (chunk_size > min_chunk_size);
193
194 mp = njs_zalloc(sizeof(njs_mp_t) + slots * sizeof(njs_mp_slot_t));
195
196 if (njs_fast_path(mp != NULL)) {
197 mp->page_size = page_size;
198 mp->page_alignment = njs_max(page_alignment, NJS_MAX_ALIGNMENT);
199 mp->cluster_size = cluster_size;
200
201 slot = mp->slots;
202
203 do {
204 njs_queue_init(&slot->pages);
205
206 slot->size = chunk_size;
207 /* slot->chunks should be one less than actual number of chunks. */
208 slot->chunks = (page_size / chunk_size) - 1;
209
210 slot++;
211 chunk_size *= 2;
212 } while (chunk_size < page_size);
213
214 mp->chunk_size_shift = njs_mp_shift(min_chunk_size);
215 mp->page_size_shift = njs_mp_shift(page_size);
216
217 njs_rbtree_init(&mp->blocks, njs_mp_rbtree_compare);
218
219 njs_queue_init(&mp->free_pages);
220 }
221
222 return mp;
223 }
224
225
226 static njs_uint_t
njs_mp_shift(njs_uint_t n)227 njs_mp_shift(njs_uint_t n)
228 {
229 njs_uint_t shift;
230
231 shift = 0;
232 n /= 2;
233
234 do {
235 shift++;
236 n /= 2;
237 } while (n != 0);
238
239 return shift;
240 }
241
242
243 njs_bool_t
njs_mp_is_empty(njs_mp_t * mp)244 njs_mp_is_empty(njs_mp_t *mp)
245 {
246 return (njs_rbtree_is_empty(&mp->blocks)
247 && njs_queue_is_empty(&mp->free_pages));
248 }
249
250
251 void
njs_mp_destroy(njs_mp_t * mp)252 njs_mp_destroy(njs_mp_t *mp)
253 {
254 void *p;
255 njs_mp_block_t *block;
256 njs_mp_cleanup_t *c;
257 njs_rbtree_node_t *node, *next;
258
259 njs_debug_alloc("mp destroy\n");
260
261 for (c = mp->cleanup; c != NULL; c = c->next) {
262 if (c->handler != NULL) {
263 njs_debug_alloc("mp run cleanup: @%p\n", c);
264 c->handler(c->data);
265 }
266 }
267
268 next = njs_rbtree_root(&mp->blocks);
269
270 while (next != njs_rbtree_sentinel(&mp->blocks)) {
271
272 node = njs_rbtree_destroy_next(&mp->blocks, &next);
273 block = (njs_mp_block_t *) node;
274
275 p = block->start;
276
277 if (block->type != NJS_MP_EMBEDDED_BLOCK) {
278 njs_free(block);
279 }
280
281 njs_free(p);
282 }
283
284 njs_free(mp);
285 }
286
287
288 void *
njs_mp_alloc(njs_mp_t * mp,size_t size)289 njs_mp_alloc(njs_mp_t *mp, size_t size)
290 {
291 njs_debug_alloc("mp alloc: %uz\n", size);
292
293 #if !(NJS_DEBUG_MEMORY)
294
295 if (size <= mp->page_size) {
296 return njs_mp_alloc_small(mp, size);
297 }
298
299 #endif
300
301 return njs_mp_alloc_large(mp, NJS_MAX_ALIGNMENT, size);
302 }
303
304
305 void *
njs_mp_zalloc(njs_mp_t * mp,size_t size)306 njs_mp_zalloc(njs_mp_t *mp, size_t size)
307 {
308 void *p;
309
310 p = njs_mp_alloc(mp, size);
311
312 if (njs_fast_path(p != NULL)) {
313 njs_memzero(p, size);
314 }
315
316 return p;
317 }
318
319
320 void *
njs_mp_align(njs_mp_t * mp,size_t alignment,size_t size)321 njs_mp_align(njs_mp_t *mp, size_t alignment, size_t size)
322 {
323 njs_debug_alloc("mp align: @%uz:%uz\n", alignment, size);
324
325 /* Alignment must be a power of 2. */
326
327 if (njs_fast_path(njs_is_power_of_two(alignment))) {
328
329 #if !(NJS_DEBUG_MEMORY)
330
331 if (size <= mp->page_size && alignment <= mp->page_alignment) {
332 size = njs_max(size, alignment);
333
334 if (size <= mp->page_size) {
335 return njs_mp_alloc_small(mp, size);
336 }
337 }
338
339 #endif
340
341 return njs_mp_alloc_large(mp, alignment, size);
342 }
343
344 return NULL;
345 }
346
347
348 void *
njs_mp_zalign(njs_mp_t * mp,size_t alignment,size_t size)349 njs_mp_zalign(njs_mp_t *mp, size_t alignment, size_t size)
350 {
351 void *p;
352
353 p = njs_mp_align(mp, alignment, size);
354
355 if (njs_fast_path(p != NULL)) {
356 njs_memzero(p, size);
357 }
358
359 return p;
360 }
361
362
363 #if !(NJS_DEBUG_MEMORY)
364
365 njs_inline u_char *
njs_mp_page_addr(njs_mp_t * mp,njs_mp_page_t * page)366 njs_mp_page_addr(njs_mp_t *mp, njs_mp_page_t *page)
367 {
368 njs_mp_block_t *block;
369
370 block = (njs_mp_block_t *)
371 ((u_char *) page - page->number * sizeof(njs_mp_page_t)
372 - offsetof(njs_mp_block_t, pages));
373
374 return block->start + (page->number << mp->page_size_shift);
375 }
376
377
378 static void *
njs_mp_alloc_small(njs_mp_t * mp,size_t size)379 njs_mp_alloc_small(njs_mp_t *mp, size_t size)
380 {
381 u_char *p;
382 njs_mp_page_t *page;
383 njs_mp_slot_t *slot;
384 njs_queue_link_t *link;
385
386 p = NULL;
387
388 if (size <= mp->page_size / 2) {
389
390 /* Find a slot with appropriate chunk size. */
391 for (slot = mp->slots; slot->size < size; slot++) { /* void */ }
392
393 size = slot->size;
394
395 if (njs_fast_path(!njs_queue_is_empty(&slot->pages))) {
396
397 link = njs_queue_first(&slot->pages);
398 page = njs_queue_link_data(link, njs_mp_page_t, link);
399
400 p = njs_mp_page_addr(mp, page);
401 p += njs_mp_alloc_chunk(page->map, size);
402
403 page->chunks--;
404
405 if (page->chunks == 0) {
406 /*
407 * Remove full page from the mp chunk slot list
408 * of pages with free chunks.
409 */
410 njs_queue_remove(&page->link);
411 }
412
413 } else {
414 page = njs_mp_alloc_page(mp);
415
416 if (njs_fast_path(page != NULL)) {
417
418 njs_queue_insert_head(&slot->pages, &page->link);
419
420 /* Mark the first chunk as busy. */
421 page->map[0] = 0x80;
422 page->map[1] = 0;
423 page->map[2] = 0;
424 page->map[3] = 0;
425
426 /* slot->chunks are already one less. */
427 page->chunks = slot->chunks;
428 page->size = size >> mp->chunk_size_shift;
429
430 p = njs_mp_page_addr(mp, page);
431 }
432 }
433
434 } else {
435 page = njs_mp_alloc_page(mp);
436
437 if (njs_fast_path(page != NULL)) {
438 page->size = mp->page_size >> mp->chunk_size_shift;
439
440 p = njs_mp_page_addr(mp, page);
441 }
442
443 #if (NJS_DEBUG)
444 size = mp->page_size;
445 #endif
446 }
447
448 njs_debug_alloc("mp chunk:%uz alloc: %p\n", size, p);
449
450 return p;
451 }
452
453
454 static njs_uint_t
njs_mp_alloc_chunk(uint8_t * map,njs_uint_t size)455 njs_mp_alloc_chunk(uint8_t *map, njs_uint_t size)
456 {
457 uint8_t mask;
458 njs_uint_t n, offset;
459
460 offset = 0;
461 n = 0;
462
463 /* The page must have at least one free chunk. */
464
465 for ( ;; ) {
466 if (map[n] != 0xff) {
467
468 mask = 0x80;
469
470 do {
471 if ((map[n] & mask) == 0) {
472 /* A free chunk is found. */
473 map[n] |= mask;
474 return offset;
475 }
476
477 offset += size;
478 mask >>= 1;
479
480 } while (mask != 0);
481
482 } else {
483 /* Fast-forward: all 8 chunks are occupied. */
484 offset += size * 8;
485 }
486
487 n++;
488 }
489 }
490
491
492 static njs_mp_page_t *
njs_mp_alloc_page(njs_mp_t * mp)493 njs_mp_alloc_page(njs_mp_t *mp)
494 {
495 njs_mp_page_t *page;
496 njs_mp_block_t *cluster;
497 njs_queue_link_t *link;
498
499 if (njs_queue_is_empty(&mp->free_pages)) {
500 cluster = njs_mp_alloc_cluster(mp);
501 if (njs_slow_path(cluster == NULL)) {
502 return NULL;
503 }
504 }
505
506 link = njs_queue_first(&mp->free_pages);
507 njs_queue_remove(link);
508
509 page = njs_queue_link_data(link, njs_mp_page_t, link);
510
511 return page;
512 }
513
514
515 static njs_mp_block_t *
njs_mp_alloc_cluster(njs_mp_t * mp)516 njs_mp_alloc_cluster(njs_mp_t *mp)
517 {
518 njs_uint_t n;
519 njs_mp_block_t *cluster;
520
521 n = mp->cluster_size >> mp->page_size_shift;
522
523 cluster = njs_zalloc(sizeof(njs_mp_block_t) + n * sizeof(njs_mp_page_t));
524
525 if (njs_slow_path(cluster == NULL)) {
526 return NULL;
527 }
528
529 /* NJS_MP_CLUSTER_BLOCK type is zero. */
530
531 cluster->size = mp->cluster_size;
532
533 cluster->start = njs_memalign(mp->page_alignment, mp->cluster_size);
534 if (njs_slow_path(cluster->start == NULL)) {
535 njs_free(cluster);
536 return NULL;
537 }
538
539 n--;
540 cluster->pages[n].number = n;
541 njs_queue_insert_head(&mp->free_pages, &cluster->pages[n].link);
542
543 while (n != 0) {
544 n--;
545 cluster->pages[n].number = n;
546 njs_queue_insert_before(&cluster->pages[n + 1].link,
547 &cluster->pages[n].link);
548 }
549
550 njs_rbtree_insert(&mp->blocks, &cluster->node);
551
552 return cluster;
553 }
554
555 #endif
556
557
558 static void *
njs_mp_alloc_large(njs_mp_t * mp,size_t alignment,size_t size)559 njs_mp_alloc_large(njs_mp_t *mp, size_t alignment, size_t size)
560 {
561 u_char *p;
562 size_t aligned_size;
563 uint8_t type;
564 njs_mp_block_t *block;
565
566 /* Allocation must be less than 4G. */
567 if (njs_slow_path(size >= UINT32_MAX)) {
568 return NULL;
569 }
570
571 if (njs_is_power_of_two(size)) {
572 block = njs_malloc(sizeof(njs_mp_block_t));
573 if (njs_slow_path(block == NULL)) {
574 return NULL;
575 }
576
577 p = njs_memalign(alignment, size);
578 if (njs_slow_path(p == NULL)) {
579 njs_free(block);
580 return NULL;
581 }
582
583 type = NJS_MP_DISCRETE_BLOCK;
584
585 } else {
586 aligned_size = njs_align_size(size, sizeof(uintptr_t));
587
588 p = njs_memalign(alignment, aligned_size + sizeof(njs_mp_block_t));
589 if (njs_slow_path(p == NULL)) {
590 return NULL;
591 }
592
593 block = (njs_mp_block_t *) (p + aligned_size);
594 type = NJS_MP_EMBEDDED_BLOCK;
595 }
596
597 block->type = type;
598 block->size = size;
599 block->start = p;
600
601 njs_rbtree_insert(&mp->blocks, &block->node);
602
603 return p;
604 }
605
606
607 static intptr_t
njs_mp_rbtree_compare(njs_rbtree_node_t * node1,njs_rbtree_node_t * node2)608 njs_mp_rbtree_compare(njs_rbtree_node_t *node1, njs_rbtree_node_t *node2)
609 {
610 njs_mp_block_t *block1, *block2;
611
612 block1 = (njs_mp_block_t *) node1;
613 block2 = (njs_mp_block_t *) node2;
614
615 return (uintptr_t) block1->start - (uintptr_t) block2->start;
616 }
617
618
619 njs_mp_cleanup_t *
njs_mp_cleanup_add(njs_mp_t * mp,size_t size)620 njs_mp_cleanup_add(njs_mp_t *mp, size_t size)
621 {
622 njs_mp_cleanup_t *c;
623
624 c = njs_mp_alloc(mp, sizeof(njs_mp_cleanup_t));
625 if (njs_slow_path(c == NULL)) {
626 return NULL;
627 }
628
629 if (size) {
630 c->data = njs_mp_alloc(mp, size);
631 if (njs_slow_path(c->data == NULL)) {
632 return NULL;
633 }
634
635 } else {
636 c->data = NULL;
637 }
638
639 c->handler = NULL;
640 c->next = mp->cleanup;
641
642 mp->cleanup = c;
643
644 njs_debug_alloc("mp add cleanup: @%p\n", c);
645
646 return c;
647 }
648
649
650 void
njs_mp_free(njs_mp_t * mp,void * p)651 njs_mp_free(njs_mp_t *mp, void *p)
652 {
653 const char *err;
654 njs_mp_block_t *block;
655
656 njs_debug_alloc("mp free: @%p\n", p);
657
658 block = njs_mp_find_block(&mp->blocks, p);
659
660 if (njs_fast_path(block != NULL)) {
661
662 if (block->type == NJS_MP_CLUSTER_BLOCK) {
663 err = njs_mp_chunk_free(mp, block, p);
664
665 if (njs_fast_path(err == NULL)) {
666 return;
667 }
668
669 } else if (njs_fast_path(p == block->start)) {
670 njs_rbtree_delete(&mp->blocks, &block->node);
671
672 if (block->type == NJS_MP_DISCRETE_BLOCK) {
673 njs_free(block);
674 }
675
676 njs_free(p);
677
678 return;
679
680 } else {
681 err = "freed pointer points to middle of block: %p\n";
682 }
683
684 } else {
685 err = "freed pointer is out of mp: %p\n";
686 }
687
688 njs_debug_alloc(err, p);
689 }
690
691
692 static njs_mp_block_t *
njs_mp_find_block(njs_rbtree_t * tree,u_char * p)693 njs_mp_find_block(njs_rbtree_t *tree, u_char *p)
694 {
695 njs_mp_block_t *block;
696 njs_rbtree_node_t *node, *sentinel;
697
698 node = njs_rbtree_root(tree);
699 sentinel = njs_rbtree_sentinel(tree);
700
701 while (node != sentinel) {
702
703 block = (njs_mp_block_t *) node;
704
705 if (p < block->start) {
706 node = node->left;
707
708 } else if (p >= block->start + block->size) {
709 node = node->right;
710
711 } else {
712 return block;
713 }
714 }
715
716 return NULL;
717 }
718
719
720 static const char *
njs_mp_chunk_free(njs_mp_t * mp,njs_mp_block_t * cluster,u_char * p)721 njs_mp_chunk_free(njs_mp_t *mp, njs_mp_block_t *cluster,
722 u_char *p)
723 {
724 u_char *start;
725 uintptr_t offset;
726 njs_uint_t n, size, chunk;
727 njs_mp_page_t *page;
728 njs_mp_slot_t *slot;
729
730 n = (p - cluster->start) >> mp->page_size_shift;
731 start = cluster->start + (n << mp->page_size_shift);
732
733 page = &cluster->pages[n];
734
735 if (page->size == 0) {
736 return "freed pointer points to already free page: %p";
737 }
738
739 size = page->size << mp->chunk_size_shift;
740
741 if (size != mp->page_size) {
742
743 offset = (uintptr_t) (p - start) & (mp->page_size - 1);
744 chunk = offset / size;
745
746 if (njs_slow_path(offset != chunk * size)) {
747 return "freed pointer points to wrong chunk: %p";
748 }
749
750 if (njs_slow_path(njs_mp_chunk_is_free(page->map, chunk))) {
751 return "freed pointer points to already free chunk: %p";
752 }
753
754 njs_mp_chunk_set_free(page->map, chunk);
755
756 /* Find a slot with appropriate chunk size. */
757 for (slot = mp->slots; slot->size < size; slot++) { /* void */ }
758
759 if (page->chunks != slot->chunks) {
760 page->chunks++;
761
762 if (page->chunks == 1) {
763 /*
764 * Add the page to the head of mp chunk slot list
765 * of pages with free chunks.
766 */
767 njs_queue_insert_head(&slot->pages, &page->link);
768 }
769
770 njs_mp_free_junk(p, size);
771
772 return NULL;
773
774 } else {
775 /*
776 * All chunks are free, remove the page from mp chunk slot
777 * list of pages with free chunks.
778 */
779 njs_queue_remove(&page->link);
780 }
781
782 } else if (njs_slow_path(p != start)) {
783 return "invalid pointer to chunk: %p";
784 }
785
786 /* Add the free page to the mp's free pages tree. */
787
788 page->size = 0;
789 njs_queue_insert_head(&mp->free_pages, &page->link);
790
791 njs_mp_free_junk(p, size);
792
793 /* Test if all pages in the cluster are free. */
794
795 page = cluster->pages;
796 n = mp->cluster_size >> mp->page_size_shift;
797
798 do {
799 if (page->size != 0) {
800 return NULL;
801 }
802
803 page++;
804 n--;
805 } while (n != 0);
806
807 /* Free cluster. */
808
809 page = cluster->pages;
810 n = mp->cluster_size >> mp->page_size_shift;
811
812 do {
813 njs_queue_remove(&page->link);
814 page++;
815 n--;
816 } while (n != 0);
817
818 njs_rbtree_delete(&mp->blocks, &cluster->node);
819
820 p = cluster->start;
821
822 njs_free(cluster);
823 njs_free(p);
824
825 return NULL;
826 }
827