红黑树 IN Linux （一）

struct rb_augment_callbacks {
	void (*propagate)(struct rb_node *node, struct rb_node *stop);
	void (*copy)(struct rb_node *old, struct rb_node *new);
	void (*rotate)(struct rb_node *old, struct rb_node *new);
};

struct vm_area_struct {
        /* The first cache line has the info for VMA tree walking. */

        unsigned long vm_start;         /* Our start address within vm_mm. */
        unsigned long vm_end;           /* The first byte after our end address
                                           within vm_mm. */

        /* linked list of VM areas per task, sorted by address */
        struct vm_area_struct *vm_next, *vm_prev;

        struct rb_node vm_rb;

        /*
         * Largest free memory gap in bytes to the left of this VMA.
         * Either between this VMA and vma->vm_prev, or between one of the
         * VMAs below us in the VMA rbtree and its ->vm_prev. This helps
         * get_unmapped_area find a free area of the right size.
         */
        unsigned long rb_subtree_gap;

        ...

// http://lxr.free-electrons.com/source/mm/mmap.c?v=4.7#L371
RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
                     unsigned long, rb_subtree_gap, vma_compute_subtree_gap)

// http://lxr.free-electrons.com/source/include/linux/rbtree_augmented.h?v=4.7#L63
#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,       \
                             rbtype, rbaugmented, rbcompute)            \
...                                                                     \
static void                                                             \
rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)       \
{                                                                       \
        rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);            \
        rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);            \
        new->rbaugmented = old->rbaugmented;                            \
        old->rbaugmented = rbcompute(old);                              \
}                                                                       \
rbstatic const struct rb_augment_callbacks rbname = {                   \
        rbname ## _propagate, rbname ## _copy, rbname ## _rotate        \
}; 

static long vma_compute_subtree_gap(struct vm_area_struct *vma)
{
        unsigned long max, subtree_gap;
        max = vma->vm_start;
        if (vma->vm_prev)
                max -= vma->vm_prev->vm_end;
        if (vma->vm_rb.rb_left) {
                subtree_gap = rb_entry(vma->vm_rb.rb_left,
                                struct vm_area_struct, vm_rb)->rb_subtree_gap;
                if (subtree_gap > max)
                        max = subtree_gap;
        }
        if (vma->vm_rb.rb_right) {
                subtree_gap = rb_entry(vma->vm_rb.rb_right,
                                struct vm_area_struct, vm_rb)->rb_subtree_gap;
                if (subtree_gap > max)
                        max = subtree_gap;
        }
        return max;
}

# 前提假定：待分配的空间，要么可在 P 名下空隙找到；要么没有符合要求的空闲空间
# 伪代码描述：找 P 名下满足分配要求、地址最低的空隙
#
# 出场变量简介：
#   length: 分配请求的长度，对齐到`对齐要求'
#   high_limit: vm_unmapped_area_info.high_limit - length
#   low_limit:  vm_unmapped_area_info.low_limit + length
#
# 要求：
#   gap_start <= high_limit
#   gap_end >= low_limit
#   gap_end - gap_start >= length
 
 
# http://lxr.free-electrons.com/source/mm/mmap.c?v=4.7#L1621
gap_end = P.vm_start                # i.e. G3.end

gap_end >= low_limit && P.rb_left && P.rb_left.rb_subtree_gap >= length?
                                    # P.rb_left is L
                                    # L.rb_subtree_gap = max(G1.size, G2.size)
# answer: yes, Try P.L
	### Current is L !
	gap_end = L.vm_start        # i.e. G1.end
 
	# L 没有左子节点
 
	# check_current: http://lxr.free-electrons.com/source/mm/mmap.c?v=4.7#L1634
	gap_start = 0               # i.e. G1.start
	if (gap_start > high_limit) # 检查：gap_start 必小于等于 high_limit
		return not found!!! # 不满足返回 not found !!! 这是因为剩余待查的空隙，其 gap_start 只会更大！
	  
	gap_end >= low_limit?       # i.e. G1.end >= low_limit? answer: no
 
	# Try P.L.T
	# http://lxr.free-electrons.com/source/mm/mmap.c?v=4.7#L1641
		### Current is T !
		gap_end = T.vm_start  # i.e. G2.end
		
		# T 没有左子节点

		# check_current
		gap_start = L.end     # i.e. G2.start
		if (gap_start > high_limit)
			return not found!!!
		gap_end >= low_limit? # i.e. G2.end >= low_limit? answer: no
		
		# T 没有右子节点
		
		# 向上返回...直到返回 P 继续
		# 对应代码：http://lxr.free-electrons.com/source/mm/mmap.c?v=4.7#L1652
 
 
### Current is P !
gap_start = T.vm_end                # i.e. G3.start
gap_end = P.vm_start                # i.e. G3.end
# check_current
if (gap_start > high_limit)
	return not found!!!
gap_end >= low_limit?               # answer: yes
gap_end - gap_start >= length?      # i.e. G3.size > length? answer: no
 
# Try P.R
	### Current is R !
	gap_end = R.vm_start        # i.e. G4.end
 
	# R 没有左子节点
 
	# check_current
	gap_start = P.end           # i.e. G4.start
	if (gap_start > high_limit)
		return not found!!!
	gap_end >= low_limit?       # answer: yes
	gap_end - gap_start >= length? # i.e. G4.size > length? answer: yes
	 
	# found !!!