From 0de21341f9ee2fcf6292afc816ffacdab79b85f3 Mon Sep 17 00:00:00 2001 From: Shell Date: Fri, 3 Mar 2023 11:51:21 +0800 Subject: [fix] mm bugs (#7010) * [fix] implementation fault on avl * [fix] mm may free varea allocated statically * [test] add test and benchmark for avl --- components/mm/avl_adpt.h | 3 ++ components/mm/mm_aspace.c | 77 +++++++++++++++++++++++++++++---------- components/mm/mm_flag.h | 2 + components/utilities/libadt/avl.c | 25 +++++++++---- 4 files changed, 80 insertions(+), 27 deletions(-) (limited to 'components') diff --git a/components/mm/avl_adpt.h b/components/mm/avl_adpt.h index f58c9974fb..9ee827932c 100644 --- a/components/mm/avl_adpt.h +++ b/components/mm/avl_adpt.h @@ -21,8 +21,11 @@ ? rt_container_of(rt_container_of(pnode, struct _aspace_node, node), \ struct rt_varea, node) \ : 0 + #define ASPACE_VAREA_NEXT(pva) (VAREA_ENTRY(util_avl_next(&pva->node.node))) #define ASPACE_VAREA_FIRST(aspace) (VAREA_ENTRY(util_avl_first(&aspace->tree.tree))) +#define ASPACE_VAREA_LAST(aspace) (VAREA_ENTRY(util_avl_last(&aspace->tree.tree))) +#define ASPACE_VAREA_PREV(pva) (VAREA_ENTRY(util_avl_prev(&pva->node.node))) typedef struct _aspace_node { diff --git a/components/mm/mm_aspace.c b/components/mm/mm_aspace.c index aadf36e06b..b42cdfb5a4 100644 --- a/components/mm/mm_aspace.c +++ b/components/mm/mm_aspace.c @@ -65,6 +65,24 @@ static inline void _varea_post_install(rt_varea_t varea, rt_aspace_t aspace, varea->mem_obj->on_varea_open(varea); } +/* restore context modified by varea install */ +static inline void _varea_uninstall(rt_varea_t varea) +{ + rt_aspace_t aspace = varea->aspace; + + if (varea->mem_obj && varea->mem_obj->on_varea_close) + varea->mem_obj->on_varea_close(varea); + + rt_varea_free_pages(varea); + + WR_LOCK(aspace); + _aspace_bst_remove(aspace, varea); + WR_UNLOCK(aspace); + + rt_hw_mmu_unmap(aspace, varea->start, varea->size); + rt_hw_tlb_invalidate_range(aspace, varea->start, varea->size, ARCH_PAGE_SIZE); +} + int _init_lock(rt_aspace_t aspace) { MM_PGTBL_LOCK_INIT(aspace); @@ -144,12 +162,18 @@ static int _do_named_map(rt_aspace_t aspace, void *vaddr, rt_size_t length, { /* TODO try to map with huge TLB, when flag & HUGEPAGE */ rt_size_t pgsz = ARCH_PAGE_SIZE; - rt_hw_mmu_map(aspace, vaddr, phyaddr, pgsz, attr); + void *ret = rt_hw_mmu_map(aspace, vaddr, phyaddr, pgsz, attr); + if (ret == RT_NULL) + { + err = -RT_ERROR; + break; + } vaddr += pgsz; phyaddr += pgsz; } - rt_hw_tlb_invalidate_range(aspace, vaddr, length, ARCH_PAGE_SIZE); + if (err == RT_EOK) + rt_hw_tlb_invalidate_range(aspace, end - length, length, ARCH_PAGE_SIZE); return err; } @@ -265,6 +289,7 @@ static int _mm_aspace_map(rt_aspace_t aspace, rt_varea_t varea, rt_size_t attr, if (mem_obj->hint_free) { + /* mem object can control mapping range and so by modifing hint */ mem_obj->hint_free(&hint); } @@ -273,17 +298,27 @@ static int _mm_aspace_map(rt_aspace_t aspace, rt_varea_t varea, rt_size_t attr, if (err == RT_EOK) { + /* fill in varea data */ _varea_post_install(varea, aspace, attr, flags, mem_obj, offset); if (MMF_TEST_CNTL(flags, MMF_PREFETCH)) { + /* do the MMU & TLB business */ err = _do_prefetch(aspace, varea, varea->start, varea->size); + if (err) + { + /* restore data structure and MMU */ + _varea_uninstall(varea); + } } } return err; } +#define _IS_OVERFLOW(start, length) ((length) > (0ul - (uintptr_t)(start))) +#define _IS_OVERSIZE(start, length, limit_s, limit_sz) (((length) + (rt_size_t)((start) - (limit_start))) > (limit_size)) + static inline int _not_in_range(void *start, rt_size_t length, void *limit_start, rt_size_t limit_size) { @@ -291,8 +326,8 @@ static inline int _not_in_range(void *start, rt_size_t length, LOG_D("%s: [%p : %p] [%p : %p]", __func__, start, length, limit_start, limit_size); /* assuming (base + length) will not overflow except (0) */ return start != RT_NULL - ? ((length > (0ul - (uintptr_t)start)) || start < limit_start || - (length + (rt_size_t)(start - limit_start)) > limit_size) + ? (_IS_OVERFLOW(start, length) || start < limit_start || + _IS_OVERSIZE(start, length, limit_start, limit_size)) : length > limit_size; } @@ -334,6 +369,10 @@ int rt_aspace_map(rt_aspace_t aspace, void **addr, rt_size_t length, if (varea) { err = _mm_aspace_map(aspace, varea, attr, flags, mem_obj, offset); + if (err != RT_EOK) + { + rt_free(varea); + } } else { @@ -374,6 +413,7 @@ int rt_aspace_map_static(rt_aspace_t aspace, rt_varea_t varea, void **addr, { varea->size = length; varea->start = *addr; + flags |= MMF_STATIC_ALLOC; err = _mm_aspace_map(aspace, varea, attr, flags, mem_obj, offset); } @@ -430,8 +470,7 @@ int _mm_aspace_map_phy(rt_aspace_t aspace, rt_varea_t varea, if (err != RT_EOK) { - _aspace_unmap(aspace, varea->start, varea->size); - rt_free(varea); + _varea_uninstall(varea); } } } @@ -486,7 +525,7 @@ int rt_aspace_map_phy_static(rt_aspace_t aspace, rt_varea_t varea, { varea->start = hint->prefer; varea->size = hint->map_size; - hint->flags |= MMF_MAP_FIXED; + hint->flags |= (MMF_MAP_FIXED | MMF_STATIC_ALLOC); LOG_D("%s: start %p size %p phy at %p", __func__, varea->start, varea->size, pa_off << MM_PAGE_SHIFT); err = _mm_aspace_map_phy(aspace, varea, hint, attr, pa_off, ret_va); } @@ -502,21 +541,19 @@ void _aspace_unmap(rt_aspace_t aspace, void *addr, rt_size_t length) { struct _mm_range range = {addr, addr + length - 1}; rt_varea_t varea = _aspace_bst_search_overlap(aspace, range); - while (varea) - { - if (varea->mem_obj && varea->mem_obj->on_varea_close) - varea->mem_obj->on_varea_close(varea); - - rt_varea_free_pages(varea); - - WR_LOCK(aspace); - _aspace_bst_remove(aspace, varea); - WR_UNLOCK(aspace); - rt_hw_mmu_unmap(aspace, varea->start, varea->size); - rt_hw_tlb_invalidate_range(aspace, varea->start, varea->size, ARCH_PAGE_SIZE); + if (varea == RT_NULL) + { + LOG_I("%s: No such entry found at %p with %lx bytes\n", __func__, addr, length); + } - rt_free(varea); + while (varea) + { + _varea_uninstall(varea); + if (!(varea->flag & MMF_STATIC_ALLOC)) + { + rt_free(varea); + } varea = _aspace_bst_search_overlap(aspace, range); } } diff --git a/components/mm/mm_flag.h b/components/mm/mm_flag.h index 4f15415159..1d5130cc45 100644 --- a/components/mm/mm_flag.h +++ b/components/mm/mm_flag.h @@ -51,6 +51,8 @@ enum mm_flag_cntl MMF_TEXT = _DEF_FLAG(5), + MMF_STATIC_ALLOC = _DEF_FLAG(6), + /** * @brief a non-locked memory can be swapped out when required, this is * reserved for future diff --git a/components/utilities/libadt/avl.c b/components/utilities/libadt/avl.c index 9f4d84af2c..0b474b1f9e 100644 --- a/components/utilities/libadt/avl.c +++ b/components/utilities/libadt/avl.c @@ -51,9 +51,11 @@ static inline void midmount_right(struct util_avl_struct *axis, lrchild->avl_left = lchild; lrchild->avl_right = axis; + lrchild->height = lchild->height; lchild->height = lrheight; axis->height = lrheight; + lrchild->parent = axis->parent; lchild->parent = lrchild; axis->parent = lrchild; if (lchild->avl_right != NULL) @@ -70,7 +72,7 @@ static inline void rotate_left(struct util_avl_struct *axis, size_t rlheight) { axis->avl_right = rlchild; - rchild->avl_right = axis; + rchild->avl_left = axis; axis->height = rlheight + 1; rchild->height = axis->height + 1; @@ -94,9 +96,11 @@ static inline void midmount_left(struct util_avl_struct *axis, rlchild->avl_right = rchild; rlchild->avl_left = axis; + rlchild->height = rchild->height; rchild->height = rlheight; axis->height = rlheight; + rlchild->parent = axis->parent; rchild->parent = rlchild; axis->parent = rlchild; if (rchild->avl_left != NULL) @@ -125,7 +129,7 @@ void util_avl_rebalance(struct util_avl_struct *node, { struct util_avl_struct *lchild = axis->avl_left; struct util_avl_struct *rchild = axis->avl_right; - nodeplace = node->parent ? NODE_PLACE(axis) : &root->root_node; + nodeplace = axis->parent ? NODE_PLACE(axis) : &root->root_node; int lheight = HEIGHT_OF(lchild); int rheight = HEIGHT_OF(rchild); if (rheight + 1 < lheight) @@ -135,10 +139,12 @@ void util_avl_rebalance(struct util_avl_struct *node, if (HEIGHT_OF(lchild->avl_left) >= lrheight) { rotate_right(axis, lchild, lrchild, nodeplace, lrheight); + axis = lchild->parent; } else { midmount_right(axis, lchild, lrchild, nodeplace, lrheight); + axis = lrchild->parent; } } else if (lheight + 1 < rheight) @@ -148,20 +154,23 @@ void util_avl_rebalance(struct util_avl_struct *node, if (HEIGHT_OF(rchild->avl_right) >= rlheight) { rotate_left(axis, rchild, rlchild, nodeplace, rlheight); + axis = rchild->parent; } else { midmount_left(axis, rchild, rlchild, nodeplace, rlheight); + axis = rlchild->parent; } } else { - int height = lheight < rheight ? rheight : lheight; + int height = (lheight < rheight ? rheight : lheight) + 1; if (height == axis->height) break; axis->height = height; + axis = axis->parent; } - } while (nodeplace != &root->root_node); + } while (axis); } void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root) @@ -196,9 +205,10 @@ void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root) *nodeplace = rchild; rchild->avl_left = node->avl_left; if (rchild->avl_left != NULL) - rchild->avl_left->parent = node->parent; + rchild->avl_left->parent = rchild; rchild->parent = node->parent; - node = rchild; + util_avl_rebalance(rchild, root); + node = rchild->parent; } else { @@ -221,7 +231,8 @@ void util_avl_remove(struct util_avl_struct *node, struct util_avl_root *root) if (sparent->avl_left != NULL) sparent->avl_left->parent = sparent; successor->parent = node->parent; - node = sparent; + util_avl_rebalance(sparent, root); + node = successor; } } -- cgit v1.3.1