From: Rich Felker <dalias@libc.org>
To: musl@lists.openwall.com
Subject: [musl] mallocng progress and growth chart
Date: Sun, 10 May 2020 14:09:34 -0400 [thread overview]
Message-ID: <20200510180934.GV21576@brightrain.aerifal.cx> (raw)
[-- Attachment #1: Type: text/plain, Size: 2188 bytes --]
I just pushed a big queued set of changes to mallocng, including some
directions that didn't go well and were mostly reversed but with
improvements to the old. These include:
- Fixes to definitions of some size classes where counts didn't fit in
a power-of-two sized mmap or containing-group.
- Fixing bad interaction between realloc and coarse size classing
(always causing malloc-memcpy-free due to size class not matching;
this was what was making apk and some other things painfully slow).
- Coarse size classing down to class 4 (except 6->7). This tends to
save memory in low-usage programs.
- Improvements to logic for single-slot and low-count groups to avoid
situations that waste lots of memory as well as ones that
unnecessarily do eagar allocation.
- Flipping definition/dependency of aligned_alloc/memalign so that
legacy nonstd function is not used in definition of std functions.
- New bounce counter with sequence numbers and decay, so that bounces
with lots of intervening expensive (mmap/munmap) ops don't get
accounted, and classes in bouncing state (retaining a free group
unnecessarily to avoid cost of un- and re-mapping) can return to
non-bouncing state.
I've also hacked up a test program that probes and prints the growth
sequence at each size just below a step in size class or page
boundary. This is intended to verify that the emergent behavior from
the allocation strategy rules in mallocng isn't doing anything
horribly stupid.
For each size, 200 mallocs are performed and if the result is the
start of a new group, the size/type of the allocation is printed. The
form 'NxZ' indicates a normal group of N slots each of slot size Z
(Z-4 usable). The form 'Nk' indicates a single-slot group where the
mapping length (N kB) is less than the nominal slot size; it shows
places where the strategy chose to use individual mmap below the hard
mmap threshold to save space and preserve individual freeability. (And
in principle these allocations should be amenable to mremap for
realloc, but it's not used yet.)
Source (with nasty poking at implementation internals, so build with
-no-builtin or -ffreestanding) is also attached.
Rich
[-- Attachment #2: growth.c --]
[-- Type: text/plain, Size: 1549 bytes --]
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/wait.h>
struct meta {
struct meta *prev, *next;
struct group *mem;
volatile int avail_mask, freed_mask;
uintptr_t last_idx:5;
uintptr_t freeable:1;
uintptr_t sizeclass:6;
uintptr_t maplen:8*sizeof(uintptr_t)-12;
};
const uint16_t size_classes[] = {
1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 12, 15,
18, 20, 25, 31,
36, 42, 50, 63,
72, 84, 102, 127,
146, 170, 204, 255,
292, 340, 409, 511,
584, 682, 818, 1023,
1169, 1364, 1637, 2047,
2340, 2730, 3276, 4095,
4680, 5460, 6552, 8191,
};
void runtest(size_t size)
{
pid_t pid;
if ((pid=fork())) {
waitpid(pid, 0, 0);
return;
}
unsigned char *p, *ptrs[200];
printf("%5zu: ", size);
for (int i=0; i<sizeof ptrs / sizeof *ptrs; i++) {
ptrs[i] = p = malloc(size);
int idx = p[-3] & 31;
struct meta *m = *(struct meta **)(p-16-*(uint16_t *)(p-2)*16);
if (idx==0) {
if (!m->maplen || m->maplen*4096UL>=size_classes[m->sizeclass]*16+16)
printf(" %2dx%-5d", m->last_idx+1, size_classes[m->sizeclass]*16);
else
printf(" %7luk", m->maplen*4UL);
} else {
//printf("[ ]");
}
}
for (int i=0; i<sizeof ptrs / sizeof *ptrs; i++) free(ptrs[i]);
printf("\n");
exit(0);
}
int main() {
if (1) for (int i=0; i<44; i++) {
size_t size = size_classes[i]*16;
runtest(size-4);
size_t pgaligned = (size+4095) & -4096;
if (pgaligned != size+16 && pgaligned < size_classes[i+1]*16)
runtest(pgaligned-20);
}
// runtest(4076);
// runtest(4076);
// runtest(4076);
}
[-- Attachment #3: growth.txt --]
[-- Type: text/plain, Size: 13062 bytes --]
12: 30x16 30x16 30x16 30x16 30x16 30x16 30x16
28: 15x32 15x32 15x32 15x32 15x32 15x32 15x32 15x32 15x32 31x32 31x32 31x32
44: 10x48 10x48 10x48 10x48 10x48 10x48 10x48 10x48 20x48 20x48 20x48 20x48 20x48 20x48
60: 7x64 7x64 7x64 7x64 7x64 7x64 7x64 7x64 7x64 15x64 15x64 15x64 15x64 15x64 31x64 31x64
76: 5x96 5x96 6x80 6x80 6x80 6x80 6x80 6x80 6x80 6x80 12x80 12x80 12x80 12x80 12x80 25x80 25x80 25x80 25x80
92: 5x96 5x96 5x96 5x96 5x96 5x96 5x96 5x96 10x96 10x96 10x96 10x96 10x96 21x96 21x96 21x96 21x96 21x96 21x96
108: 4x112 4x112 4x112 4x112 4x112 4x112 4x112 4x112 8x112 8x112 8x112 8x112 8x112 18x112 18x112 18x112 18x112 18x112 18x112 18x112 18x112
124: 7x128 7x128 7x128 7x128 7x128 7x128 7x128 7x128 7x128 15x128 15x128 15x128 15x128 15x128 31x128 31x128
140: 3x160 3x160 3x160 3x160 6x144 6x144 6x144 6x144 6x144 6x144 6x144 6x144 6x144 6x144 14x144 14x144 14x144 14x144 28x144 28x144 28x144
156: 3x160 3x160 3x160 3x160 3x160 3x160 3x160 3x160 6x160 6x160 6x160 6x160 12x160 12x160 12x160 12x160 24x160 24x160 24x160 24x160 24x160
188: 2x240 2x240 2x240 2x240 2x240 5x192 5x192 5x192 5x192 5x192 5x192 5x192 5x192 10x192 10x192 10x192 10x192 20x192 20x192 20x192 20x192 20x192 20x192
236: 2x240 2x240 2x240 2x240 2x240 2x240 2x240 2x240 4x240 4x240 4x240 4x240 8x240 8x240 8x240 8x240 16x240 16x240 16x240 16x240 32x240 32x240 32x240
284: 3x320 3x320 3x320 3x320 7x288 7x288 7x288 7x288 7x288 7x288 7x288 7x288 14x288 14x288 14x288 14x288 28x288 28x288 28x288
316: 3x320 3x320 3x320 3x320 3x320 3x320 3x320 3x320 6x320 6x320 6x320 6x320 12x320 12x320 12x320 12x320 24x320 24x320 24x320 24x320 24x320
396: 2x496 2x496 2x496 2x496 2x496 5x400 5x400 5x400 5x400 5x400 5x400 5x400 5x400 10x400 10x400 10x400 10x400 20x400 20x400 20x400 20x400 20x400 20x400
492: 2x496 2x496 2x496 2x496 2x496 2x496 2x496 2x496 4x496 4x496 4x496 4x496 8x496 8x496 8x496 8x496 16x496 16x496 16x496 16x496 32x496 32x496 32x496
572: 3x672 3x672 3x672 3x672 7x576 7x576 7x576 7x576 7x576 7x576 7x576 7x576 14x576 14x576 14x576 14x576 28x576 28x576 28x576
668: 3x672 3x672 3x672 3x672 3x672 3x672 3x672 3x672 6x672 6x672 6x672 6x672 12x672 12x672 12x672 12x672 24x672 24x672 24x672 24x672 24x672
796: 2x1008 2x1008 2x1008 2x1008 2x1008 5x800 5x800 5x800 5x800 5x800 5x800 5x800 5x800 10x800 10x800 10x800 10x800 20x800 20x800 20x800 20x800 20x800 20x800
1004: 2x1008 2x1008 2x1008 2x1008 2x1008 2x1008 2x1008 2x1008 4x1008 4x1008 4x1008 4x1008 8x1008 8x1008 8x1008 8x1008 16x1008 16x1008 16x1008 16x1008 32x1008 32x1008 32x1008
1148: 3x1344 3x1344 3x1344 3x1344 7x1152 7x1152 7x1152 7x1152 7x1152 7x1152 7x1152 7x1152 14x1152 14x1152 14x1152 14x1152 28x1152 28x1152 28x1152
1340: 3x1344 3x1344 3x1344 3x1344 3x1344 3x1344 3x1344 3x1344 6x1344 6x1344 6x1344 6x1344 12x1344 12x1344 12x1344 12x1344 24x1344 24x1344 24x1344 24x1344 24x1344
1628: 2x2032 2x2032 2x2032 2x2032 2x2032 5x1632 5x1632 5x1632 5x1632 5x1632 5x1632 5x1632 5x1632 10x1632 10x1632 10x1632 10x1632 20x1632 20x1632 20x1632 20x1632 20x1632 20x1632
2028: 2x2032 2x2032 2x2032 2x2032 2x2032 2x2032 2x2032 2x2032 4x2032 4x2032 4x2032 4x2032 8x2032 8x2032 8x2032 8x2032 16x2032 16x2032 16x2032 16x2032 32x2032 32x2032 32x2032
2332: 3x2720 3x2720 3x2720 3x2720 5x2336 5x2336 5x2336 5x2336 5x2336 5x2336 7x2336 7x2336 7x2336 7x2336 14x2336 14x2336 14x2336 14x2336 28x2336 28x2336 28x2336
2716: 3x2720 3x2720 3x2720 3x2720 3x2720 3x2720 3x2720 3x2720 6x2720 6x2720 6x2720 6x2720 12x2720 12x2720 12x2720 12x2720 24x2720 24x2720 24x2720 24x2720 24x2720
3260: 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 2x4080 5x3264 5x3264 5x3264 5x3264 5x3264 5x3264 5x3264 5x3264 10x3264 10x3264 10x3264 10x3264 20x3264 20x3264 20x3264 20x3264 20x3264 20x3264
4076: 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 1x4080 2x4080 2x4080 2x4080 2x4080 4x4080 4x4080 4x4080 4x4080 8x4080 8x4080 8x4080 8x4080 16x4080 16x4080 16x4080 16x4080 32x4080 32x4080 32x4080
4668: 2x5440 2x5440 2x5440 2x5440 2x5440 5x4672 5x4672 5x4672 5x4672 5x4672 5x4672 7x4672 7x4672 7x4672 7x4672 14x4672 14x4672 14x4672 14x4672 28x4672 28x4672 28x4672
5436: 2x5440 2x5440 2x5440 2x5440 2x5440 2x5440 3x5440 3x5440 3x5440 3x5440 6x5440 6x5440 6x5440 6x5440 12x5440 12x5440 12x5440 12x5440 24x5440 24x5440 24x5440 24x5440 24x5440
6540: 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 2x8176 3x6544 3x6544 3x6544 3x6544 3x6544 3x6544 3x6544 5x6544 5x6544 5x6544 5x6544 10x6544 10x6544 10x6544 10x6544 20x6544 20x6544 20x6544 20x6544 20x6544 20x6544
8172: 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 1x8176 2x8176 2x8176 2x8176 2x8176 4x8176 4x8176 4x8176 4x8176 8x8176 8x8176 8x8176 8x8176 16x8176 16x8176 16x8176 16x8176 32x8176 32x8176 32x8176
9340: 2x10912 2x10912 2x10912 2x10912 2x10912 3x9344 3x9344 3x9344 3x9344 3x9344 3x9344 3x9344 3x9344 3x9344 3x9344 7x9344 7x9344 7x9344 7x9344 14x9344 14x9344 14x9344 14x9344 28x9344 28x9344 28x9344
10908: 2x10912 2x10912 2x10912 2x10912 2x10912 2x10912 3x10912 3x10912 3x10912 3x10912 6x10912 6x10912 6x10912 6x10912 12x10912 12x10912 12x10912 12x10912 24x10912 24x10912 24x10912 24x10912 24x10912
12268: 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 12k 10x13088 10x13088 10x13088 10x13088 20x13088 20x13088 20x13088 20x13088 20x13088 20x13088
13084: 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 2x16368 1x13088 1x13088 1x13088 1x13088 1x13088 1x13088 3x13088 3x13088 3x13088 3x13088 3x13088 5x13088 5x13088 5x13088 5x13088 10x13088 10x13088 10x13088 10x13088 20x13088 20x13088 20x13088 20x13088 20x13088 20x13088
16364: 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 1x16368 2x16368 2x16368 2x16368 2x16368 4x16368 4x16368 4x16368 4x16368 8x16368 8x16368 8x16368 8x16368 16x16368 16x16368 16x16368 16x16368 32x16368 32x16368 32x16368
18700: 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 1x18704 1x18704 1x18704 1x18704 1x18704 1x18704 3x18704 3x18704 3x18704 3x18704 3x18704 3x18704 3x18704 3x18704 7x18704 7x18704 7x18704 7x18704 14x18704 14x18704 14x18704 14x18704 28x18704 28x18704 28x18704
20460: 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 20k 12x21824 12x21824 12x21824 12x21824 24x21824 24x21824 24x21824 24x21824 24x21824
21820: 1x21824 1x21824 1x21824 1x21824 2x21824 2x21824 2x21824 2x21824 3x21824 3x21824 3x21824 3x21824 6x21824 6x21824 6x21824 6x21824 12x21824 12x21824 12x21824 12x21824 24x21824 24x21824 24x21824 24x21824 24x21824
24556: 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 24k 10x26192 10x26192 10x26192 10x26192 20x26192 20x26192 20x26192 20x26192 20x26192 20x26192
26188: 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 1x26192 1x26192 1x26192 1x26192 1x26192 1x26192 3x26192 3x26192 3x26192 3x26192 3x26192 5x26192 5x26192 5x26192 5x26192 10x26192 10x26192 10x26192 10x26192 20x26192 20x26192 20x26192 20x26192 20x26192 20x26192
28652: 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 28k 8x32752 8x32752 8x32752 8x32752 16x32752 16x32752 16x32752 16x32752 32x32752 32x32752 32x32752
32748: 1x32752 1x32752 1x32752 1x32752 1x32752 1x32752 1x32752 1x32752 2x32752 2x32752 2x32752 2x32752 4x32752 4x32752 4x32752 4x32752 8x32752 8x32752 8x32752 8x32752 16x32752 16x32752 16x32752 16x32752 32x32752 32x32752 32x32752
37436: 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 1x37440 1x37440 1x37440 1x37440 1x37440 1x37440 3x37440 3x37440 3x37440 3x37440 3x37440 3x37440 3x37440 3x37440 7x37440 7x37440 7x37440 7x37440 14x37440 14x37440 14x37440 14x37440 28x37440 28x37440 28x37440
40940: 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 40k 12x43680 12x43680 12x43680 12x43680 24x43680 24x43680 24x43680 24x43680 24x43680
43676: 1x43680 1x43680 1x43680 1x43680 2x43680 2x43680 2x43680 2x43680 3x43680 3x43680 3x43680 3x43680 6x43680 6x43680 6x43680 6x43680 12x43680 12x43680 12x43680 12x43680 24x43680 24x43680 24x43680 24x43680 24x43680
45036: 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 44k 10x52416 10x52416 10x52416 10x52416 20x52416 20x52416 20x52416 20x52416 20x52416 20x52416
52412: 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 1x52416 1x52416 1x52416 1x52416 1x52416 1x52416 3x52416 3x52416 3x52416 3x52416 3x52416 5x52416 5x52416 5x52416 5x52416 10x52416 10x52416 10x52416 10x52416 20x52416 20x52416 20x52416 20x52416 20x52416 20x52416
53228: 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 52k 8x65520 8x65520 8x65520 8x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520
65516: 1x65520 1x65520 1x65520 1x65520 1x65520 1x65520 1x65520 1x65520 2x65520 2x65520 2x65520 2x65520 4x65520 4x65520 4x65520 4x65520 8x65520 8x65520 8x65520 8x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520 16x65520
next reply other threads:[~2020-05-10 18:09 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-10 18:09 Rich Felker [this message]
2020-05-11 17:51 ` Rich Felker
2020-05-16 0:29 ` Rich Felker
2020-05-16 3:29 ` Rich Felker
2020-05-17 3:30 ` Rich Felker
2020-05-18 18:53 ` Rich Felker
2020-05-25 15:45 ` Pirmin Walthert
2020-05-25 17:54 ` Rich Felker
2020-05-25 18:13 ` Pirmin Walthert
2020-06-04 7:04 ` Pirmin Walthert
2020-06-04 15:11 ` Rich Felker
2020-05-18 18:35 ` Rich Felker
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200510180934.GV21576@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).