全部博文（22）
分类： C/C++
2009-05-26 15:49:20
3620. /* allocate a large request from the best fitting chunk in a treebin */
MAX_SMALL_REQUEST对齐值<= nb < MAX_REQUEST对齐值
3621. static void* tmalloc_large(mstate m, size_t nb) {
3622. tchunkptr v = 0;
设置初始值，注意rsize是size_t类型变量，因此一个很小的负数事实上是一个很大的正数。
3623. size_t rsize = -nb; /* Unsigned negation */
3624. tchunkptr t;
3625. bindex_t idx;
计算nb字节数所对应的dltree树结构。
3626. compute_tree_index(nb, idx);
3627.
该dltree树结构不为空，即存在和nb字节数同在一个箱子内（不理解“同在一个箱子内”则请查看前面讲解dltree内容部分）的空闲chunk块。
3628. if ((t = *treebin_at(m, idx)) != 0) {
3629. /* Traverse tree for this bin looking for node with size == nb */
遍历dltree试图找到一个size==nb的空闲chunk块。
前面曾经讲到过dltree就是关键码只有0和1的Trie树。并且根据treebins箱的分法，0号箱和1号箱的关键码都只需7位长（因为其范围为128，表xxx的第二列），2号箱和3号箱的关键码都只需8位长（因为其范围为256，表xxx的第二列），……，依次类似。
宏leftshift_for_tree_index(idx)计算的是32 减去 idx号箱对应的关键码长度 的值。
#define leftshift_for_tree_index(i) \
((i == NTREEBINS-1)? 0 : \
((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
#define NTREEBINS (32U)
#define SIZE_T_BITSIZE (sizeof(size_t) << 3)
#define TREEBIN_SHIFT (8U)
#define SIZE_T_ONE ((size_t)1)
直接来看具体的值吧，依旧是32位平台下：
箱号idx => leftshift_for_tree_index(idx)值
0=>25
1=>25
2=>24
3=>24
4=>23
5=>23
6=>22
7=>22
8=>21
9=>21
10=>20
11=>20
12=>19
13=>19
14=>18
15=>18
16=>17
17=>17
18=>16
19=>16
20=>15
21=>15
22=>14
23=>14
24=>13
25=>13
26=>12
27=>12
28=>11
29=>11
30=>10
31=>0
因此下面这个sizebits的值就是将nb中起关键码作用的位移到最左边的结果值。
3630. size_t sizebits = nb << leftshift_for_tree_index(idx);
3631. tchunkptr rst = 0; /* The deepest untaken right subtree */
3632. for (;;) {
3633. tchunkptr rt;
相差多大？
宏chunksize用于计算chunk块大小。
#define chunksize(p) ((p)->head & ~(INUSE_BITS))
3634. size_t trem = chunksize(t) - nb;
比之前选定的chunk块更合适？
3635. if (trem < rsize) {
3636. v = t;
没有比它更合适的了，就是它了。
3637. if ((rsize = trem) == 0)
3638. break;
3639. }
记录当前节点的右子树根节点。
3640. rt = t->child[1];
根据关键码值进入相应的子树。
3641. t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
rst保存包含有最接近nb字节数大小chunk块的dltree子树。
3642. if (rt != 0 && rt != t)
3643. rst = rt;
将要继续查找的子树为空，则保存rst到t，然后跳出for循环。
3644. if (t == 0) {
3645. t = rst; /* set t to least subtree holding sizes > nb */
3646. break;
3647. }
3648. sizebits <<= 1;
3649. }
3650. }
3651.
t和v都为0表示请求字节大小对应的treebin为空，因此只有在更大的箱号内查找。
3652. if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
和前面的某些代码类似，计算包含大于请求字节数目chunk块的所有箱号对应掩码。
3653. binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
存在。
3654. if (leftbits != 0) {
3655. bindex_t i;
选择最合适的分箱。
3656. binmap_t leastbit = least_bit(leftbits);
计算对应箱号。
3657. compute_bit2idx(leastbit, i);
箱子对应dltree根节点。
3658. t = *treebin_at(m, i);
3659. }
3660. }
3661.
执行到这已经可以确定以t为根节点的dltree中所有chunk块都可满足申请请求，下面这个循环只不过试图在这个dltree中找到一个最合适的chunk块来用于内存分配。最合适的chunk块被保存在变量v内。
3662. while (t != 0) { /* find smallest of tree or subtree */
3663. size_t trem = chunksize(t) - nb;
3664. if (trem < rsize) {
3665. rsize = trem;
3666. v = t;
3667. }
leftmost_child宏优先选取左子树，在左子树为空的情况下则选取右子树。
#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
3668. t = leftmost_child(t);
3669. }
3670.
3671. /* If dv is a better fit, return 0 so malloc will use it */
前面在treebins中选择的chunk块存在（即变量v不为空），并且它比dv chunk块更适合（即选择的chunk块大小比dv chunk块大小更接近当前请求字节数目）用于内存分配以服务当前申请请求。如果dv chunk块更适合用来分配，则本函数将返回0，因此会在返回到dlmalloc函数内再进行在dv chunk块的内存分配操作。
3672. if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
下面同样是分割、组建新chunk块、设置边界标记等，在此不再累述。
3673. if (RTCHECK(ok_address(m, v))) { /* split */
3674. mchunkptr r = chunk_plus_offset(v, nb);
3675. assert(chunksize(v) == rsize + nb);
3676. if (RTCHECK(ok_next(v, r))) {
3677. unlink_large_chunk(m, v);
3678. if (rsize < MIN_CHUNK_SIZE)
3679. set_inuse_and_pinuse(m, v, (rsize + nb));
3680. else {
3681. set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3682. set_size_and_pinuse_of_free_chunk(r, rsize);
3683. insert_chunk(m, r, rsize);
3684. }
3685. return chunk2mem(v);
3686. }
3687. }
3688. CORRUPTION_ERROR_ACTION(m);
3689. }
3690. return 0;
3691. }
3692.
3322. /* Get memory from system using MORECORE or MMAP */
3323. static void* sys_alloc(mstate m, size_t nb) {
3324. char* tbase = CMFAIL;
3325. size_t tsize = 0;
3326. flag_t mmap_flag = 0;
3327.
相关设置值的初始化。
3328. init_mparams();
3329.
3330. /* Directly map large chunks */
dlmalloc向系统申请内存有两种方式：一为ORECORE（使用函数sbrk()）方式；一为MMAP（使用函数mmap()）方式。由于MMAP方式一般都是取到不连续的内存空间，因此只有在某些情况下（见下面）才使用它。
如果设置允许调用mmap函数并且字节数nb已超过了预设的可以调用mmap界限则利用mmap函数向系统申请内存。
3331. if (use_mmap(m) && nb >= mparams.mmap_threshold) {
3332. void* mem = mmap_alloc(m, nb);
3333. if (mem != 0)
3334. return mem;
3335. }
3336.
根据相对优劣排序依次按照如下三种方法从系统获取内存：
1，利用MORECORE分配连续空间
2，利用MMAP分配新空间
3，利用MORECORE分配不连续空间
3337. /*
3338. Try getting memory in any of three ways (in most-preferred to
3339. least-preferred order):
3340. 1. A call to MORECORE that can normally contiguously extend memory.
3341. (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
3342. or main space is mmapped or a previous contiguous call failed)
3343. 2. A call to MMAP new space (disabled if not HAVE_MMAP).
3344. Note that under the default settings, if MORECORE is unable to
3345. fulfill a request, and HAVE_MMAP is true, then mmap is
3346. used as a noncontiguous system allocator. This is a useful backup
3347. strategy for systems with holes in address spaces -- in this case
3348. sbrk cannot contiguously expand the heap, but mmap may be able to
3349. find space.
3350. 3. A call to MORECORE that cannot usually contiguously extend memory.
3351. (disabled if not HAVE_MORECORE)
3352. */
3353.
宏use_noncontiguous定义如下：
#define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
3354. if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
试图利用MORECORE分配连续空间
3355. char* br = CMFAIL;
函数segment_holding()用于查找某一内存地址所属于的segment段。具体代码如下，我们可以看到所谓的查找就是简单的线性扫描查找。
/* Return segment holding given address */
static msegmentptr segment_holding(mstate m, char* addr) {
msegmentptr sp = &m->seg;
for (;;) {
if (addr >= sp->base && addr < sp->base + sp->size)
return sp;
if ((sp = sp->next) == 0)
return 0;
}
}
3356. msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
3357. size_t asize = 0;
上锁。
3358. ACQUIRE_MORECORE_LOCK();
3359.
top chunk块为空，即第一次分配情况。
3360. if (ss == 0) { /* First time through or recovery */
获取内存的当前边界点（即所谓的当前中断点）。CALL_MORECORE间接的调用sbrk()函数。函数sbrk()移动设置新的当前中断点并返回设置之前的中断点。
#define CALL_MORECORE(S) MORECORE(S)
extern void* sbrk(ptrdiff_t);
3361. char* base = (char*)CALL_MORECORE(0);
3362. if (base != CMFAIL) {
进行对齐处理，这里的对齐一般以一个内存页大小（32位平台下，大部分情况是4K）为基准，也可自由设置，比如64K。
3363. asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3364. /* Adjust to end on a page boundary */
起始边界不是页对齐，则需要将末尾边界调整为页对齐。
#define is_page_aligned(S)\
(((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
#define page_align(S)\
(((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
3365. if (!is_page_aligned(base))
3366. asize += (page_align((size_t)base) - (size_t)base);
3367. /* Can't call MORECORE if size is negative when treated as signed */
asize需要小于HALF_MAX_SIZE_T，sbrk()函数的参数是有符号的，如果大于HALF_MAX_SIZE_T，则传到sbrk()函数内部则成了负数。
#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
#define MAX_SIZE_T (~(size_t)0)
3368. if (asize < HALF_MAX_SIZE_T &&
3369. (br = (char*)(CALL_MORECORE(asize))) == base) {
利用MORECORE分配连续空间成功。
3370. tbase = base;
3371. tsize = asize;
3372. }
3373. }
3374. }
3375. else {
top chunk块存在的情况。
3376. /* Subtract out existing available top space from MORECORE request. */
3377. asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);
3378. /* Use mem here only if it did continuously extend old space */
3379. if (asize < HALF_MAX_SIZE_T &&
3380. (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
3381. tbase = br;
3382. tsize = asize;
3383. }
3384. }
3385.
部分操作失败的处理。
3386. if (tbase == CMFAIL) { /* Cope with partial failure */
3387. if (br != CMFAIL) { /* Try to use/extend the space we did get */
3388. if (asize < HALF_MAX_SIZE_T &&
3389. asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {
3390. size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);
3391. if (esize < HALF_MAX_SIZE_T) {
3392. char* end = (char*)CALL_MORECORE(esize);
3393. if (end != CMFAIL)
3394. asize += esize;
3395. else { /* Can't use; try to release */
3396. CALL_MORECORE(-asize);
3397. br = CMFAIL;
3398. }
3399. }
3400. }
3401. }
3402. if (br != CMFAIL) { /* Use the space we did get */
3403. tbase = br;
3404. tsize = asize;
3405. }
如果本次试图申请连续内存空间失败，则再次申请内存时候就直接放弃这种尝试。
#define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
3406. else
3407. disable_contiguous(m); /* Don't try contiguous path in the future */
3408. }
3409.
解锁。
3410. RELEASE_MORECORE_LOCK();
3411. }
3412.
尝试利用mmap申请内存空间。
3413. if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
3414. size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
3415. size_t rsize = granularity_align(req);
3416. if (rsize > nb) { /* Fail if wraps around zero */
CALL_MMAP宏定义：
#define CALL_MMAP(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
3417. char* mp = (char*)(CALL_MMAP(rsize));
3418. if (mp != CMFAIL) {
3419. tbase = mp;
3420. tsize = rsize;
3421. mmap_flag = IS_MMAPPED_BIT;
3422. }
3423. }
3424. }
3425.
尝试利用MORECORE申请不连续内存空间。
3426. if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
3427. size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3428. if (asize < HALF_MAX_SIZE_T) {
3429. char* br = CMFAIL;
3430. char* end = CMFAIL;
3431. ACQUIRE_MORECORE_LOCK();
3432. br = (char*)(CALL_MORECORE(asize));
3433. end = (char*)(CALL_MORECORE(0));
3434. RELEASE_MORECORE_LOCK();
3435. if (br != CMFAIL && end != CMFAIL && br < end) {
3436. size_t ssize = end - br;
3437. if (ssize > nb + TOP_FOOT_SIZE) {
3438. tbase = br;
3439. tsize = ssize;
3440. }
3441. }
3442. }
3443. }
3444.
对新分配内存进行处理，牵扯到的变量比较多，处理也比较繁琐，但是都比较简单，因此也没有什么特别好讲解的，在此略过。
3445. if (tbase != CMFAIL) {
3446.
3447. if ((m->footprint += tsize) > m->max_footprint)
3448. m->max_footprint = m->footprint;
3449.
3450. if (!is_initialized(m)) { /* first-time initialization */
3451. m->seg.base = m->least_addr = tbase;
3452. m->seg.size = tsize;
3453. m->seg.sflags = mmap_flag;
3454. m->magic = mparams.magic;
3455. init_bins(m);
3456. if (is_global(m))
3457. init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3458. else {
3459. /* Offset top by embedded malloc_state */
3460. mchunkptr mn = next_chunk(mem2chunk(m));
3461. init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
3462. }
3463. }
3464.
3465. else {
3466. /* Try to merge with an existing segment */
3467. msegmentptr sp = &m->seg;
3468. while (sp != 0 && tbase != sp->base + sp->size)
3469. sp = sp->next;
3470. if (sp != 0 &&
3471. !is_extern_segment(sp) &&
3472. (sp->sflags & IS_MMAPPED_BIT) == mmap_flag &&
3473. segment_holds(sp, m->top)) { /* append */
3474. sp->size += tsize;
3475. init_top(m, m->top, m->topsize + tsize);
3476. }
3477. else {
3478. if (tbase < m->least_addr)
3479. m->least_addr = tbase;
3480. sp = &m->seg;
3481. while (sp != 0 && sp->base != tbase + tsize)
3482. sp = sp->next;
3483. if (sp != 0 &&
3484. !is_extern_segment(sp) &&
3485. (sp->sflags & IS_MMAPPED_BIT) == mmap_flag) {
3486. char* oldbase = sp->base;
3487. sp->base = tbase;
3488. sp->size += tsize;
3489. return prepend_alloc(m, tbase, oldbase, nb);
3490. }
3491. else
3492. add_segment(m, tbase, tsize, mmap_flag);
3493. }
3494. }
3495.
3496. if (nb < m->topsize) { /* Allocate from new or extended top space */
3497. size_t rsize = m->topsize -= nb;
3498. mchunkptr p = m->top;
3499. mchunkptr r = m->top = chunk_plus_offset(p, nb);
3500. r->head = rsize | PINUSE_BIT;
3501. set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3502. check_top_chunk(m, m->top);
3503. check_malloced_chunk(m, chunk2mem(p), nb);
3504. return chunk2mem(p);
3505. }
3506. }
3507.
3508. MALLOC_FAILURE_ACTION;
3509. return 0;
3510. }
