genalloc 是 linux 內核提供的通用內存分配器，源碼位於 lib/genalloc.c。這個分配器為獨立於內核以外的內存塊提供分配方法，采用的是最先適配原則，android 最新的 ION 內存管理器對 ION_HEAP_TYPE_CARVEOUT 類型的內存就是采用的這個分配器。 1、基礎數據結構 首先看下分配器用到的幾個數據結構，struct gen_pool 用來描述一個內存池： [cpp] struct gen_pool { rwlock_t lock; /* 鏈表讀寫鎖 */ struct list_head chunks; /* 內存池中內存塊的鏈表 */ int min_alloc_order; /* 內存池最小分配單元的階數，大小為 2^min_alloc_order */ }; 在使用的時候需要向內存池中加入內存塊，一個內存塊即一大塊連續的物理內存，用 struct gen_pool_chunk 來描述： [cpp] struct gen_pool_chunk { spinlock_t lock; /* 操作內存塊時用到的自旋鎖 */ struct list_head next_chunk; /* 加入內存池的節點 */ unsigned long start_addr; /* 內存塊的起始地址 */ unsigned long end_addr; /* 內存塊的結束地址 */ unsigned long bits[0]; /* 內存塊的位圖 */ }; 2、函數接口及調用方法 genalloc 用到的函數接口有下面幾個： [cpp] /* 創建一個內存池，主要工作是完成 struct gen_pool 的初始化 */ struct gen_pool *gen_pool_create(int min_alloc_order, int nid); /* 向內存池中加入內存塊，addr 為起始地址，size 為大小 */ int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size, int nid); /* 銷毀一個內存池 */ void gen_pool_destroy(struct gen_pool *pool); /* 內存池分配內存的函數 */ unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size); /* 內存池釋放內存的函數 */ void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size); 對通用內存分配器的一般使用方法如下： [cpp] /* 初始化內存池，需要創建以及加入內存塊，參數為：起始地址、大小、最小分配階數 */ static void *mm_init(uint32_t addr, uint32_t size, uint32_t order) { struct gen_pool *pool; pool = gen_pool_create(order, 0); if (pool == NULL) { return NULL; } if (gen_pool_add(pool, addr, size, 0) != 0) { gen_pool_destroy(pool); return NULL; } return pool; } /* 銷毀內存池 */ static void mm_exit(void *handle) { gen_pool_destroy(handle); } /* 分配函數 */ static uint32_t mm_alloc(void *handle, uint32_t size) { return gen_pool_alloc(handle, size); } /* 釋放函數 */ static void mm_free(void *handle, uint32_t addr, uint32_t size) { return gen_pool_free(handle, addr, size); } /* 提供給上一級內存管理器調用 */ struct xxx_mem_ops mm_ops = { .init = mm_init, .exit = mm_exit, .alloc = mm_alloc, .free = mm_free, }; 3、分配函數解析 genalloc 通過 gen_pool_alloc 函數來分配內存，下面我們分析一下這個函數的代碼： [cpp] unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size) { struct list_head *_chunk; struct gen_pool_chunk *chunk; unsigned long addr, flags; int order = pool->min_alloc_order; int nbits, bit, start_bit, end_bit; if (size == 0) return 0; nbits = (size + (1UL << order) - 1) >> order; /* 計算申請的內存需要幾個連續的最小單元 */ read_lock(&pool->lock); list_for_each(_chunk, &pool->chunks) { /* 遍歷內存池 */ chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk); end_bit = (chunk->end_addr - chunk->start_addr) >> order; /* 計算當前內存池長度 */ end_bit -= nbits + 1; spin_lock_irqsave(&chunk->lock, flags); bit = -1; while (bit + 1 < end_bit) { /* 循環查找最先適配的內存區 */ bit = find_next_zero_bit(chunk->bits, end_bit, bit + 1); /* 尋找為0的bit */ if (bit >= end_bit) /* 循環結束 */ break; start_bit = bit; /* 起始位置 */ if (nbits > 1) { /* 如果申請的內存大於一個最小單元，查找連續的nbits個單元 */ bit = find_next_bit(chunk->bits, bit + nbits,bit + 1); if (bit - start_bit < nbits) continue; } addr = chunk->start_addr + ((unsigned long)start_bit << order); /* 計算申請的內存的起始地址 */ while (nbits--) __set_bit(start_bit++, chunk->bits); /* 將申請到的單元全部標記為已用 */ spin_unlock_irqrestore(&chunk->lock, flags); read_unlock(&pool->lock); return addr; } spin_unlock_irqrestore(&chunk->lock, flags); } read_unlock(&pool->lock); return 0; } 因為是用的最先適配原則，所以邏輯比較簡單，我們也可以根據自己的需求實現最適合分配器以及伙伴分配器。
