bma.c

浏览该文件的文档.

 
#include <xwos/standard.h>
#include <string.h>
#include <xwos/lib/xwlog.h>
#include <xwos/lib/bclst.h>
#include <xwos/lib/xwbop.h>
#include <xwos/osal/lock/spinlock.h>
#include <xwos/mm/common.h>
#include <xwos/mm/bma.h>
 
/* #define XWMM_BMA_LOG */ 
#if defined(XWMM_BMA_LOG)
#  define xwmm_bmalogf(lv, fmt, ...) xwlogf(lv, "BMA", fmt, ##__VA_ARGS__)
#else
#  define xwmm_bmalogf(lv, fmt, ...)
#endif
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_mem_to_bcb(struct xwmm_bma * bma, void * mem);
 
static __xwos_code
void * xwmm_bma_bcb_to_mem(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb);
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_find_buddy(struct xwmm_bma * bma,
                                          struct xwmm_bma_bcb * bcb);
 
static __xwos_code
void xwmm_bma_orderlist_add(struct xwmm_bma * bma,
                            struct xwmm_bma_orderlist * ol,
                            xwu8_t odr,
                            struct xwmm_bma_bcb * bcb);
 
static __xwos_code
xwer_t xwmm_bma_orderlist_remove(struct xwmm_bma * bma,
                                 struct xwmm_bma_orderlist * ol,
                                 xwu8_t odr,
                                 struct xwmm_bma_bcb * bcb);
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_orderlist_choose(struct xwmm_bma * bma,
                                                struct xwmm_bma_orderlist * ol);
 
static __xwos_code
void xwmm_bma_divide_block(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb,
                           xwsq_t target_odr, struct xwmm_bma_orderlist * curr_ol);
 
static __xwos_code
void xwmm_bma_combine(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb);
 
__xwos_api
xwer_t xwmm_bma_init(struct xwmm_bma * bma, const char * name,
                     xwptr_t origin, xwsz_t size,
                     xwsz_t blksize, xwsz_t blkodr)
{
        xwer_t rc;
        xwsz_t num;
        xwsz_t i;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
 
        num = 1U << blkodr;
        if (size != (num * blksize)) {
                rc = -ESIZE;
                xwmm_bmalogf(ERR, "Size of memory(0x%lX, 0x%lX) is error!\n",
                             origin, size);
                goto err_size;
        }
        bma->name = name;
        bma->zone.origin = origin;
        bma->zone.size = blksize * num;
        bma->blksize = blksize;
        bma->blkodr = blkodr;
        xwos_splk_init(&bma->lock);
        bma->orderlists = (struct xwmm_bma_orderlist *)&bma[(xwsz_t)1];
        bma->bcbs = (struct xwmm_bma_bcb *)&bma->orderlists[(xwsz_t)1 + blkodr];
        xwmm_bmalogf(DEBUG,
                     "memory:(0x%lX,0x%lX),orderlists:0x%lX,bcbs:0x%lX,"
                     "blocksize:0x%lX, blockorder:0x%lX\n",
                     origin, size, (xwptr_t)bma->orderlists, (xwptr_t)bma->bcbs,
                     bma->blksize, bma->blkodr);
 
        for (i = 0; i < num; i++) {
                bma->bcbs[i].order = XWMM_BMA_INUSED | XWMM_BMA_COMBINED;
        }
        bma->bcbs[0].order = (xwu8_t)blkodr | XWMM_BMA_INUSED;
 
        for (i = 0; i <= blkodr; i++) {
                xwlib_bclst_init_head(&bma->orderlists[i].head);
        }
        xwmm_bma_orderlist_add(bma, &bma->orderlists[blkodr], blkodr, &bma->bcbs[0]);
        return XWOK;
 
err_size:
        return rc;
}
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_mem_to_bcb(struct xwmm_bma * bma, void * mem)
{
        struct xwmm_bma_bcb * bcb;
        xwptr_t ofs;
        xwptr_t idx;
 
        ofs = (xwptr_t)mem - bma->zone.origin;
        idx = ofs / (xwptr_t)bma->blksize;
        if (ofs == (idx * bma->blksize)) {
                bcb = &bma->bcbs[idx];
        } else {
                bcb = err_ptr(-EINVAL);
        }
        return bcb;
}
 
static __xwos_code
void * xwmm_bma_bcb_to_mem(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb)
{
        xwptr_t idx;
        xwptr_t mem;
 
        idx = ((xwptr_t)bcb - (xwptr_t)bma->bcbs) / sizeof(struct xwmm_bma_bcb);
        mem = (idx * bma->blksize) + bma->zone.origin;
        return (void *)mem;
}
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_find_buddy(struct xwmm_bma * bma,
                                          struct xwmm_bma_bcb * bcb)
{
        xwsq_t seq;
        xwsq_t odr;
 
        seq = ((xwptr_t)bcb - (xwptr_t)bma->bcbs) / sizeof(struct xwmm_bma_bcb);
        odr = (xwsq_t)bcb->order & XWMM_BMA_ORDER_MASK;
        seq ^= (1U << odr);
        return &bma->bcbs[seq];
}
 
static __xwos_code
void xwmm_bma_orderlist_add(struct xwmm_bma * bma,
                            struct xwmm_bma_orderlist * ol,
                            xwu8_t odr,
                            struct xwmm_bma_bcb * bcb)
{
        struct xwlib_bclst_node * n;
 
        /* 即将加入的块不在阶链表中，是本地数据。*/
        if ((XWMM_BMA_INUSED | odr) == bcb->order) {
                n = xwmm_bma_bcb_to_mem(bma, bcb);
                xwmm_bmalogf(DEBUG,
                             "[OL:0x%lX][+] bcb(idx:0x%lX,odr:0x%X),mem(0x%lX)\n",
                             (xwptr_t)ol,
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order, (xwptr_t)n);
                xwlib_bclst_init_node(n);
                xwlib_bclst_add_head(&ol->head, n);
                /* 当块被加入到阶链表中，就变成共享数据。*/
                bcb->order &= XWMM_BMA_ORDER_MASK;
        }
}
 
static __xwos_code
xwer_t xwmm_bma_orderlist_remove(struct xwmm_bma * bma,
                                 struct xwmm_bma_orderlist * ol,
                                 xwu8_t odr,
                                 struct xwmm_bma_bcb * bcb)
{
        struct xwlib_bclst_node * n;
        xwer_t rc;
 
        XWOS_UNUSED(ol);
        n = xwmm_bma_bcb_to_mem(bma, bcb);
        xwmm_bmalogf(DEBUG,
                     "[OL:0x%lX][-] bcb(idx:0x%lX,odr:0x%X),mem(0x%lX)\n",
                     (xwptr_t)ol,
                     (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                      sizeof(struct xwmm_bma_bcb)),
                     bcb->order, (xwptr_t)n);
        /* 即将被删除的块在阶链表中，是共享数据。*/
        if (odr != bcb->order) {
                rc = -ESRCH;
        } else {
                xwlib_bclst_del_init(n);
                bcb->order |= XWMM_BMA_INUSED;
                rc = XWOK;
        }
        return rc;
}
 
static __xwos_code
struct xwmm_bma_bcb * xwmm_bma_orderlist_choose(struct xwmm_bma * bma,
                                                struct xwmm_bma_orderlist * ol)
{
        struct xwlib_bclst_node * n;
        struct xwmm_bma_bcb * bcb;
 
        if (xwlib_bclst_tst_empty(&ol->head)) {
                bcb = err_ptr(-ENOENT);
        } else {
                n = ol->head.next;
                xwlib_bclst_del_init(n);
                bcb = xwmm_bma_mem_to_bcb(bma, n);
                xwmm_bmalogf(DEBUG,
                             "[OL:0x%lX][C] bcb(idx:0x%lX,odr:0x%X)\n",
                             (xwptr_t)ol,
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order);
                /* 即将被选择的块在阶链表中，是共享数据。*/
                bcb->order |= XWMM_BMA_INUSED;
        }
        return bcb;
}
 
static __xwos_code
void xwmm_bma_divide_block(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb,
                           xwsq_t target_odr, struct xwmm_bma_orderlist * curr_ol)
{
        xwsq_t blk_odr;
        xwsq_t blk_idx;
        xwsq_t blk_ofs;
        struct xwmm_bma_bcb * buddy;
 
        blk_odr = (xwsq_t)bcb->order & XWMM_BMA_ORDER_MASK;
        blk_idx = ((xwptr_t)bcb - (xwptr_t)bma->bcbs) / sizeof(struct xwmm_bma_bcb);
 
        while (blk_odr > target_odr) {
                curr_ol--;
                blk_odr--;
                blk_ofs = 1U << blk_odr;
                buddy = &bma->bcbs[blk_idx + blk_ofs];
                /* 加入阶链表之前， `buddy` 是本地数据。*/
                XWOS_BUG_ON((XWMM_BMA_COMBINED | XWMM_BMA_INUSED) != buddy->order);
                buddy->order = (xwu8_t)blk_odr | XWMM_BMA_INUSED;
                xwmm_bma_orderlist_add(bma, curr_ol, blk_odr, buddy);
                /* `bcb` 是本地数据。*/
                bcb->order = (xwu8_t)blk_odr | XWMM_BMA_INUSED;
                xwmm_bmalogf(DEBUG,
                             "[ALLOC][D] bcb(idx:0x%lX,odr:0x%X),"
                             "buddy(idx:0x%lX,odr:0x%X)\n",
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order,
                             (((xwptr_t)buddy - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             buddy->order);
        }
}
 
__xwos_api
xwer_t xwmm_bma_alloc(struct xwmm_bma * bma, xwsq_t order, void ** membuf)
{
        xwer_t rc;
        xwreg_t flag;
        xwsq_t o;
        struct xwmm_bma_orderlist * ol;
        struct xwmm_bma_bcb * bcb;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
        XWOS_VALIDATE((order <= (xwsq_t)XWMM_BMA_MAX_ORDER), "out-of-range", -ERANGE);
 
        ol = NULL;
        bcb = err_ptr(-ENOENT);
        xwos_splk_lock_cpuirqsv(&bma->lock, &flag);
        for (o = order; o <= bma->blkodr; o++) {
                ol = &bma->orderlists[o];
                bcb = xwmm_bma_orderlist_choose(bma, ol);
                if (!is_err(bcb)) {
                        break;
                }
        }
        if (is_err(bcb)) { // cppcheck-suppress [misra-c2012-14.4]
                xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
                rc = -ENOMEM;
                *membuf = NULL;
        } else {
                xwmm_bmalogf(DEBUG,
                             "[ALLOC] bcb(idx:0x%lX,odr:0x%X)\n",
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order);
                xwmm_bma_divide_block(bma, bcb, order, ol);
                xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
                rc = XWOK;
                *membuf = xwmm_bma_bcb_to_mem(bma, bcb);
        }
        return rc;
}
 
static __xwos_code
void xwmm_bma_combine(struct xwmm_bma * bma, struct xwmm_bma_bcb * bcb)
{
        struct xwmm_bma_bcb * buddy;
        xwsq_t curr_odr;
        xwsq_t target_odr;
        xwer_t rc;
 
        curr_odr = (bcb->order & XWMM_BMA_ORDER_MASK);
        target_odr = curr_odr + (xwsq_t)1;
        while (target_odr <= bma->blkodr) {
                buddy = xwmm_bma_find_buddy(bma, bcb);
                xwmm_bmalogf(DEBUG,
                             "[FREE][M] bcb(idx:0x%lX,odr:0x%X),"
                             "buddy(idx:0x%lX,odr:0x%X)\n",
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order,
                             (((xwptr_t)buddy - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             buddy->order);
                XWOS_BUG_ON((XWMM_BMA_COMBINED | XWMM_BMA_INUSED) == buddy->order);
                rc = xwmm_bma_orderlist_remove(bma,
                                               &bma->orderlists[curr_odr],
                                               curr_odr,
                                               buddy);
                if (rc < 0) {
                        break;
                }
                /* 此时 `buddy->order` 以及 `bcb->order` 都是本地数据。 */
                if (buddy > bcb) {
                        buddy->order = XWMM_BMA_COMBINED | XWMM_BMA_INUSED;
                        bcb->order = (xwu8_t)target_odr | XWMM_BMA_INUSED;
                } else {
                        bcb->order = XWMM_BMA_COMBINED | XWMM_BMA_INUSED;
                        buddy->order = (xwu8_t)target_odr | XWMM_BMA_INUSED;
                        bcb = buddy;
                }
                curr_odr = target_odr;
                target_odr++;
        }
        xwmm_bma_orderlist_add(bma, &bma->orderlists[curr_odr], curr_odr, bcb);
}
 
__xwos_api
xwer_t xwmm_bma_free(struct xwmm_bma * bma, void * mem)
{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwreg_t flag;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
 
        if (NULL == mem) {
                rc = XWOK;
                goto do_nothing;
        }
        if ((((xwptr_t)mem < bma->zone.origin) ||
             ((xwptr_t)mem >= (bma->zone.origin + bma->zone.size)))) {
                rc = -ERANGE;
                goto err_range;
        }
        unaligned = ((xwptr_t)mem - bma->zone.origin) % (xwptr_t)bma->blksize;
        mem = (void *)((xwptr_t)mem - unaligned);
        bcb = xwmm_bma_mem_to_bcb(bma, mem);
        if (is_err(bcb)) {  // cppcheck-suppress [misra-c2012-14.4]
                rc = ptr_err(bcb);
                goto err_invalmem;
        }
        xwmm_bmalogf(DEBUG,
                     "[FREE] mem:0x%lX,bcb(idx:0x%lX,odr:0x%X)\n",
                     (xwptr_t)mem,
                     (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                      sizeof(struct xwmm_bma_bcb)),
                     bcb->order);
        if (0 == (XWMM_BMA_INUSED & bcb->order)) {
                rc = -EINVAL;
                goto err_invalmem;
        }
        xwos_splk_lock_cpuirqsv(&bma->lock, &flag);
        xwmm_bma_combine(bma, bcb);
        xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
        return XWOK;
 
err_invalmem:
err_range:
do_nothing:
        return rc;
}
 
__xwos_api
xwer_t xwmm_bma_malloc(struct xwmm_bma * bma, xwsz_t size, void ** membuf)
{
        xwer_t rc;
        xwsz_t nrblk;
        xwssq_t p2;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        if ((xwsz_t)0 == size) {
                rc = XWOK;
                *membuf = NULL;
        } else {
                nrblk = XWBOP_DIV_ROUND_UP(size, bma->blksize);
                p2 = xwbop_fls(xwsz_t, nrblk);
                while ((p2 < 0) || ((bma->blksize << (xwsz_t)p2) < size)) {
                        p2++;
                }
                rc = xwmm_bma_alloc(bma, (xwsq_t)p2, membuf);
        }
        return rc;
}
 
__xwos_api
xwer_t xwmm_bma_realloc(struct xwmm_bma * bma, xwsz_t size, void ** membuf)
{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwsz_t oldsize;
        xwer_t rc;
        void * oldm;
        void * newm;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        oldm = *membuf;
        if (NULL == oldm) {
                rc = xwmm_bma_malloc(bma, size, membuf);
        } else if ((xwsz_t)0 == size) {
                rc = xwmm_bma_free(bma, oldm);
                if (XWOK == rc) {
                        *membuf = NULL;
                }
        } else {
                if ((((xwptr_t)oldm < bma->zone.origin) ||
                     ((xwptr_t)oldm >= (bma->zone.origin + bma->zone.size)))) {
                        *membuf = NULL;
                        rc = -ERANGE;
                } else {
                        unaligned = (((xwptr_t)oldm - bma->zone.origin) %
                                     (xwptr_t)bma->blksize);
                        oldm = (void *)((xwptr_t)oldm - unaligned);
                        bcb = xwmm_bma_mem_to_bcb(bma, oldm);
                        oldsize = bcb->order & XWMM_BMA_ORDER_MASK;
                        oldsize = (1U << oldsize);
                        if (size <= oldsize) {
                                rc = XWOK;
                        } else {
                                rc = xwmm_bma_malloc(bma, size, &newm);
                                if (XWOK == rc) {
                                        // cppcheck-suppress [misra-c2012-17.7]
                                        memcpy(newm, oldm, size);
                                        *membuf = newm;
                                        xwmm_bma_free(bma, oldm);
                                } else {
                                        *membuf = NULL;
                                }
                        }
                }
        }
        return rc;
}
 
__xwos_api
xwer_t xwmm_bma_memalign(struct xwmm_bma * bma, xwsz_t alignment, xwsz_t size,
                         void ** membuf)
{
        xwssq_t p2;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        if (alignment < XWMM_ALIGNMENT) {
                alignment = XWMM_ALIGNMENT;
        }
        p2 = xwbop_fls(xwsz_t, alignment);
        while (((xwsz_t)1 << (xwsz_t)p2) < alignment) {
                p2++;
        }
        alignment = (xwsz_t)1 << (xwsz_t)p2;
        if ((xwsz_t)0 == size) {
                rc = XWOK;
                *membuf = NULL;
        } else {
                if (size <= alignment) {
                        size = alignment;
                } else {
                        p2 = xwbop_fls(xwsz_t, size);
                        while (((xwsz_t)1 << (xwsz_t)p2) < size) {
                                p2++;
                        }
                        size = ((xwsz_t)1 << (xwsz_t)p2);
                }
                /* 因BMA的特点，申请到的内存地址一定对齐到size，
                   只要size是alignment的整数倍，也一定对齐到alignment。 */
                rc = xwmm_bma_malloc(bma, size, membuf);
        }
        return rc;
}
 
xwer_t xwmm_bma_malloc_usable_size(struct xwmm_bma * bma, void * mem, xwsz_t * size)
{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwsz_t realsize;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((size), "nullptr", -EFAULT);
 
        if ((((xwptr_t)mem < bma->zone.origin) ||
             ((xwptr_t)mem >= (bma->zone.origin + bma->zone.size)))) {
                rc = -ERANGE;
        } else {
                rc = XWOK;
                unaligned = (((xwptr_t)mem - bma->zone.origin) % (xwptr_t)bma->blksize);
                mem = (void *)((xwptr_t)mem - unaligned);
                bcb = xwmm_bma_mem_to_bcb(bma, mem);
                realsize = bcb->order & XWMM_BMA_ORDER_MASK;
                realsize = (1U << realsize);
                *size = realsize;
        }
        return rc;
}