#include <rthw.h>

#include <rtthread.h>

#ifdef RT_USING_SLAB

#define DBG_TAG "kernel.slab"

#define DBG_LVL DBG_INFO

#include <rtdbg.h>

#define ZALLOC_SLAB_MAGIC 0x51ab51ab

#define ZALLOC_ZONE_LIMIT (16 * 1024) /* max slab-managed alloc */

#define ZALLOC_MIN_ZONE_SIZE (32 * 1024) /* minimum zone size */

#define ZALLOC_MAX_ZONE_SIZE (128 * 1024) /* maximum zone size */

#define ZONE_RELEASE_THRESH 2 /* threshold number of zones */

#define MIN_CHUNK_SIZE 8 /* in bytes */

#define MIN_CHUNK_MASK (MIN_CHUNK_SIZE - 1)

#define PAGE_TYPE_FREE 0x00

#define PAGE_TYPE_SMALL 0x01

#define PAGE_TYPE_LARGE 0x02

#define btokup(addr) \

(&slab->memusage[((rt_uintptr_t)(addr) - slab->heap_start) >> RT_MM_PAGE_BITS])

struct rt_slab_zone

};

struct rt_slab_chunk

{

struct rt_slab_chunk *c_next;

};

struct rt_slab_memusage

};

struct rt_slab_page

};

#define RT_SLAB_NZONES 72 /* number of zones */

struct rt_slab

};

void *rt_slab_page_alloc(rt_slab_t m, rt_size_t npages)

{

struct rt_slab_page *b, *n;

struct rt_slab_page **prev;

struct rt_slab *slab = (struct rt_slab *)m;

if (npages == 0)

return RT_NULL;

for (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next))

{

if (b->page > npages)

{

/* splite pages */

n = b + npages;

n->next = b->next;

n->page = b->page - npages;

*prev = n;

break;

}

if (b->page == npages)

{

/* this node fit, remove this node */

*prev = b->next;

break;

}

}

return b;

}

void rt_slab_page_free(rt_slab_t m, void *addr, rt_size_t npages)

{

struct rt_slab_page *b, *n;

struct rt_slab_page **prev;

struct rt_slab *slab = (struct rt_slab *)m;

RT_ASSERT(addr != RT_NULL);

RT_ASSERT((rt_uintptr_t)addr % RT_MM_PAGE_SIZE == 0);

RT_ASSERT(npages != 0);

n = (struct rt_slab_page *)addr;

for (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next))

{

RT_ASSERT(b->page > 0);

RT_ASSERT(b > n || b + b->page <= n);

if (b + b->page == n)

{

if (b + (b->page += npages) == b->next)

{

b->page += b->next->page;

b->next = b->next->next;

}

return;

}

if (b == n + npages)

{

n->page = b->page + npages;

n->next = b->next;

*prev = n;

return;

}

if (b > n + npages)

break;

}

n->page = npages;

n->next = b;

*prev = n;

}

static void rt_slab_page_init(struct rt_slab *slab, void *addr, rt_size_t npages)

{

RT_ASSERT(addr != RT_NULL);

RT_ASSERT(npages != 0);

slab->page_list = RT_NULL;

rt_slab_page_free((rt_slab_t)(&slab->parent), addr, npages);

}

rt_slab_t rt_slab_init(const char *name, void *begin_addr, rt_size_t size)

{

rt_uint32_t limsize, npages;

rt_uintptr_t start_addr, begin_align, end_align;

struct rt_slab *slab;

slab = (struct rt_slab *)RT_ALIGN((rt_uintptr_t)begin_addr, RT_ALIGN_SIZE);

start_addr = (rt_uintptr_t)slab + sizeof(*slab);

/* align begin and end addr to page */

begin_align = RT_ALIGN((rt_uintptr_t)start_addr, RT_MM_PAGE_SIZE);

end_align = RT_ALIGN_DOWN((rt_uintptr_t)begin_addr + size, RT_MM_PAGE_SIZE);

if (begin_align >= end_align)

{

rt_kprintf("slab init errr. wrong address[0x%x - 0x%x]\n",

(rt_uintptr_t)begin_addr, (rt_uintptr_t)begin_addr + size);

return RT_NULL;

}

limsize = end_align - begin_align;

npages = limsize / RT_MM_PAGE_SIZE;

LOG_D("heap[0x%x - 0x%x], size 0x%x, 0x%x pages",

begin_align, end_align, limsize, npages);

rt_memset(slab, 0, sizeof(*slab));

/* initialize slab memory object */

rt_object_init(&(slab->parent.parent), RT_Object_Class_Memory, name);

slab->parent.algorithm = "slab";

slab->parent.address = begin_align;

slab->parent.total = limsize;

slab->parent.used = 0;

slab->parent.max = 0;

slab->heap_start = begin_align;

slab->heap_end = end_align;

/* init pages */

rt_slab_page_init(slab, (void *)slab->heap_start, npages);

/* calculate zone size */

slab->zone_size = ZALLOC_MIN_ZONE_SIZE;

while (slab->zone_size < ZALLOC_MAX_ZONE_SIZE && (slab->zone_size << 1) < (limsize / 1024))

slab->zone_size <<= 1;

slab->zone_limit = slab->zone_size / 4;

if (slab->zone_limit > ZALLOC_ZONE_LIMIT)

slab->zone_limit = ZALLOC_ZONE_LIMIT;

slab->zone_page_cnt = slab->zone_size / RT_MM_PAGE_SIZE;

LOG_D("zone size 0x%x, zone page count 0x%x",

slab->zone_size, slab->zone_page_cnt);

/* allocate slab->memusage array */

limsize = npages * sizeof(struct rt_slab_memusage);

limsize = RT_ALIGN(limsize, RT_MM_PAGE_SIZE);

slab->memusage = rt_slab_page_alloc((rt_slab_t)(&slab->parent), limsize / RT_MM_PAGE_SIZE);

LOG_D("slab->memusage 0x%x, size 0x%x",

(rt_uintptr_t)slab->memusage, limsize);

return &slab->parent;

}

RTM_EXPORT(rt_slab_init);

rt_err_t rt_slab_detach(rt_slab_t m)

{

struct rt_slab *slab = (struct rt_slab *)m;

RT_ASSERT(slab != RT_NULL);

RT_ASSERT(rt_object_get_type(&slab->parent.parent) == RT_Object_Class_Memory);

RT_ASSERT(rt_object_is_systemobject(&slab->parent.parent));

rt_object_detach(&(slab->parent.parent));

return RT_EOK;

}

RTM_EXPORT(rt_slab_detach);

rt_inline int zoneindex(rt_size_t *bytes)

{

/* unsigned for shift opt */

rt_uintptr_t n = (rt_uintptr_t)(*bytes);

if (n < 128)

{

*bytes = n = (n + 7) & ~7;

/* 8 byte chunks, 16 zones */

return (n / 8 - 1);

}

if (n < 256)

{

*bytes = n = (n + 15) & ~15;

return (n / 16 + 7);

}

if (n < 8192)

{

if (n < 512)

{

*bytes = n = (n + 31) & ~31;

return (n / 32 + 15);

}

if (n < 1024)

{

*bytes = n = (n + 63) & ~63;

return (n / 64 + 23);

}

if (n < 2048)

{

*bytes = n = (n + 127) & ~127;

return (n / 128 + 31);

}

if (n < 4096)

{

*bytes = n = (n + 255) & ~255;

return (n / 256 + 39);

}

*bytes = n = (n + 511) & ~511;

return (n / 512 + 47);

}

if (n < 16384)

{

*bytes = n = (n + 1023) & ~1023;

return (n / 1024 + 55);

}

rt_kprintf("Unexpected byte count %d", n);

return 0;

}

void *rt_slab_alloc(rt_slab_t m, rt_size_t size)

{

struct rt_slab_zone *z;

rt_int32_t zi;

struct rt_slab_chunk *chunk;

struct rt_slab_memusage *kup;

struct rt_slab *slab = (struct rt_slab *)m;

/* zero size, return RT_NULL */

if (size == 0)

return RT_NULL;

/*

if (size >= slab->zone_limit)

{

size = RT_ALIGN(size, RT_MM_PAGE_SIZE);

chunk = rt_slab_page_alloc(m, size >> RT_MM_PAGE_BITS);

if (chunk == RT_NULL)

return RT_NULL;

/* set kup */

kup = btokup(chunk);

kup->type = PAGE_TYPE_LARGE;

kup->size = size >> RT_MM_PAGE_BITS;

LOG_D("alloc a large memory 0x%x, page cnt %d, kup %d",

size,

size >> RT_MM_PAGE_BITS,

((rt_uintptr_t)chunk - slab->heap_start) >> RT_MM_PAGE_BITS);

/* mem stat */

slab->parent.used += size;

if (slab->parent.used > slab->parent.max)

slab->parent.max = slab->parent.used;

return chunk;

}

/*

zi = zoneindex(&size);

RT_ASSERT(zi < RT_SLAB_NZONES);

LOG_D("try to alloc 0x%x on zone: %d", size, zi);

if ((z = slab->zone_array[zi]) != RT_NULL)

{

RT_ASSERT(z->z_nfree > 0);

/* Remove us from the zone_array[] when we become full */

if (--z->z_nfree == 0)

{

slab->zone_array[zi] = z->z_next;

z->z_next = RT_NULL;

}

/*

if (z->z_uindex + 1 != z->z_nmax)

{

z->z_uindex = z->z_uindex + 1;

chunk = (struct rt_slab_chunk *)(z->z_baseptr + z->z_uindex * size);

}

else

{

/* find on free chunk list */

chunk = z->z_freechunk;

/* remove this chunk from list */

z->z_freechunk = z->z_freechunk->c_next;

}

/* mem stats */

slab->parent.used += z->z_chunksize;

if (slab->parent.used > slab->parent.max)

slab->parent.max = slab->parent.used;

return chunk;

}

/*

{

rt_uint32_t off;

if ((z = slab->zone_free) != RT_NULL)

{

/* remove zone from free zone list */

slab->zone_free = z->z_next;

-- slab->zone_free_cnt;

}

else

{

/* allocate a zone from page */

z = rt_slab_page_alloc(m, slab->zone_size / RT_MM_PAGE_SIZE);

if (z == RT_NULL)

{

return RT_NULL;

}

LOG_D("alloc a new zone: 0x%x",

(rt_uintptr_t)z);

/* set message usage */

for (off = 0, kup = btokup(z); off < slab->zone_page_cnt; off ++)

{

kup->type = PAGE_TYPE_SMALL;

kup->size = off;

kup ++;

}

}

/* clear to zero */

rt_memset(z, 0, sizeof(struct rt_slab_zone));

/* offset of slab zone struct in zone */

off = sizeof(struct rt_slab_zone);

/*

if ((size | (size - 1)) + 1 == (size << 1))

off = (off + size - 1) & ~(size - 1);

else

off = (off + MIN_CHUNK_MASK) & ~MIN_CHUNK_MASK;

z->z_magic = ZALLOC_SLAB_MAGIC;

z->z_zoneindex = zi;

z->z_nmax = (slab->zone_size - off) / size;

z->z_nfree = z->z_nmax - 1;

z->z_baseptr = (rt_uint8_t *)z + off;

z->z_uindex = 0;

z->z_chunksize = size;

chunk = (struct rt_slab_chunk *)(z->z_baseptr + z->z_uindex * size);

/* link to zone array */

z->z_next = slab->zone_array[zi];

slab->zone_array[zi] = z;

/* mem stats */

slab->parent.used += z->z_chunksize;

if (slab->parent.used > slab->parent.max)

slab->parent.max = slab->parent.used;

}

return chunk;

}

RTM_EXPORT(rt_slab_alloc);

void *rt_slab_realloc(rt_slab_t m, void *ptr, rt_size_t size)

{

void *nptr;

struct rt_slab_zone *z;

struct rt_slab_memusage *kup;

struct rt_slab *slab = (struct rt_slab *)m;

if (ptr == RT_NULL)

return rt_slab_alloc(m, size);

if (size == 0)

{

rt_slab_free(m, ptr);

return RT_NULL;

}

/*

kup = btokup((rt_uintptr_t)ptr & ~RT_MM_PAGE_MASK);

if (kup->type == PAGE_TYPE_LARGE)

{

rt_size_t osize;

osize = kup->size << RT_MM_PAGE_BITS;

if ((nptr = rt_slab_alloc(m, size)) == RT_NULL)

return RT_NULL;

rt_memcpy(nptr, ptr, size > osize ? osize : size);

rt_slab_free(m, ptr);

return nptr;

}

else if (kup->type == PAGE_TYPE_SMALL)

{

z = (struct rt_slab_zone *)(((rt_uintptr_t)ptr & ~RT_MM_PAGE_MASK) -

kup->size * RT_MM_PAGE_SIZE);

RT_ASSERT(z->z_magic == ZALLOC_SLAB_MAGIC);

zoneindex(&size);

if (z->z_chunksize == size)

return (ptr); /* same chunk */

/*

if ((nptr = rt_slab_alloc(m, size)) == RT_NULL)

return RT_NULL;

rt_memcpy(nptr, ptr, size > z->z_chunksize ? z->z_chunksize : size);

rt_slab_free(m, ptr);

return nptr;

}

return RT_NULL;

}

RTM_EXPORT(rt_slab_realloc);

void rt_slab_free(rt_slab_t m, void *ptr)

{

struct rt_slab_zone *z;

struct rt_slab_chunk *chunk;

struct rt_slab_memusage *kup;

struct rt_slab *slab = (struct rt_slab *)m;

/* free a RT_NULL pointer */

if (ptr == RT_NULL)

return ;

/* get memory usage */

#if (DBG_LVL == DBG_LOG)

{

rt_uintptr_t addr = ((rt_uintptr_t)ptr & ~RT_MM_PAGE_MASK);

LOG_D("free a memory 0x%x and align to 0x%x, kup index %d",

(rt_uintptr_t)ptr,

(rt_uintptr_t)addr,

((rt_uintptr_t)(addr) - slab->heap_start) >> RT_MM_PAGE_BITS);

}

#endif /* DBG_LVL == DBG_LOG */

kup = btokup((rt_uintptr_t)ptr & ~RT_MM_PAGE_MASK);

/* release large allocation */

if (kup->type == PAGE_TYPE_LARGE)

{

rt_uintptr_t size;

/* clear page counter */

size = kup->size;

kup->size = 0;

/* mem stats */

slab->parent.used -= size * RT_MM_PAGE_SIZE;

LOG_D("free large memory block 0x%x, page count %d",

(rt_uintptr_t)ptr, size);

/* free this page */

rt_slab_page_free(m, ptr, size);

return;

}

/* zone case. get out zone. */

z = (struct rt_slab_zone *)(((rt_uintptr_t)ptr & ~RT_MM_PAGE_MASK) -

kup->size * RT_MM_PAGE_SIZE);

RT_ASSERT(z->z_magic == ZALLOC_SLAB_MAGIC);

chunk = (struct rt_slab_chunk *)ptr;

chunk->c_next = z->z_freechunk;

z->z_freechunk = chunk;

/* mem stats */

slab->parent.used -= z->z_chunksize;

/*

if (z->z_nfree++ == 0)

{

z->z_next = slab->zone_array[z->z_zoneindex];

slab->zone_array[z->z_zoneindex] = z;

}

/*

if (z->z_nfree == z->z_nmax &&

(z->z_next || slab->zone_array[z->z_zoneindex] != z))

{

struct rt_slab_zone **pz;

LOG_D("free zone %#x, zoneindex %d",

(rt_uintptr_t)z, z->z_zoneindex);

/* remove zone from zone array list */

for (pz = &slab->zone_array[z->z_zoneindex]; z != *pz; pz = &(*pz)->z_next)

;

*pz = z->z_next;

/* reset zone */

z->z_magic = RT_UINT32_MAX;

/* insert to free zone list */

z->z_next = slab->zone_free;

slab->zone_free = z;

++ slab->zone_free_cnt;

/* release zone to page allocator */

if (slab->zone_free_cnt > ZONE_RELEASE_THRESH)

{

register rt_uint32_t i;

z = slab->zone_free;

slab->zone_free = z->z_next;

-- slab->zone_free_cnt;

/* set message usage */

for (i = 0, kup = btokup(z); i < slab->zone_page_cnt; i ++)

{

kup->type = PAGE_TYPE_FREE;

kup->size = 0;

kup ++;

}

/* release pages */

rt_slab_page_free(m, z, slab->zone_size / RT_MM_PAGE_SIZE);

return;

}

}

}

RTM_EXPORT(rt_slab_free);

#endif /* RT_USING_SLAB */