cache
敏捷开发：
快速创建原型； 在原型基础上进行测试，总结，改进，反复 迭代，最终获得想要的结果。其中总结过程最好和他人分享，分享过程其他人的任何观点都可能打破原来的固有思维，从而使得设计获得提升。
概述
* page cache
* 存储设备访问速度远低于内存，嵌入式文件系统一般没有内置高速缓存.
* 本模块提供一个独立的高速缓存解决方案，在内存资源充足的情况下可以用于提升flash访问效率.
*
* linux的 page cache
* 和文件相关，加载文件不是一次性的。起初，只是为其分配了地址空间，address_space结构体来管理，
* 当程序运行需要用到文件数据时，会产生页失效，页失效处理会加载页面数据；
* 页面数据更新，直接更新cache里的页面，并将页面标记为dirty；
* 关闭文件或者系统空闲时会触发数据回写存储设备。
*
* 本模块用于flash驱动提升性能，cache只用来加速读取操作，写入操作建议直接写入flash。
* 写flash之前应该尝试从cache找回页面缓存，避免为同一个页面重复申请缓存。
用双向链表实现LRU数据管理，队尾存放的最久没有使用的数据节点。
用红黑树加速cache查找过程。
cache对象定义如下：
typedef struct
{
uint32_t capicity; - 最大容量
uint32_t size; - 当前有效节点数量
struct k_rbtree_root_t root; - 红黑树根节点
dlist_t head; - LRU表头
uint32_t psize; - 页尺寸
} flash_cache_t;
API
cache create
/**
* cache create
* capicity: max page sum;
* page_size: page size
* return: cache handler while success, else return NULL.
*/
cache_handler cache_create(uint32_t capicity, uint32_t page_size);
get page
/**
* get page from cache.
* address: flash page starting address.
* presence: return 0 - new page; 1 - cached page
* return: the page buffer address, if no cache page found, malloc a new one.
*/
uint8_t *cache_get_page(cache_handler cache, uint32_t address, uint32_t *presence);
add page
/**
* cache add page
* add a new page, maybe cause to release the old one.
*/
void cache_add_page(cache_handler cache, uint32_t address, uint8_t *page);
get size
/**
* cache get size
* return cached page sum.
*/
uint32_t cache_get_size(cache_handler cache);
resize
/**
* cache resize.
* used for enlarge or reduce cache size in runtime.
* size: new capicity, if 0, will be resize to (c->size/2 + 1)
*/
void cache_resize(cache_handler cache, uint32_t size)
设计详解
缓存大小自动调整
cache模块负责页面缓存申请和管理，当页面申请遇到内存不足时，自动从lru队列尾部释放一半缓存的页面。
目前是申请新页面缓存失败后启动释放，可以增加一个条件：空闲内存小于一定数目即开始缩减缓存
Linux内核的通用性考虑会有这些策略，因为内核不能确定 将来运行的环境会是什么。
对于嵌入式系统，可以将设计稍微简化一些，尤其是在运行时不能动态添加应用的系统中。
LRU队列
cache的淘汰机制 通常采用LRU队列实现。当cache满时，新的页面加入将最近最少使用的页面替换掉。
本组件LRU队列通过双向链表 实现，初始化时 根据输入的capicity创建空节点，并组装lru队列；
申请page时，根据地址信息从红黑树里面查找，如果找到，则将该节点重新放置到lru队首；
如果没有找到，则从lru队尾取回一个节点，如果该节点非空（page缓存有效），则将 该节点从红黑树移除；如果空，则分配页面；最后将节点加入红黑树；
红黑树
红黑树类似平衡二叉树，每个节点标记为红色或者黑色，在一条通往叶子节点的路径上不能有连续的红节点。插入新节点时，如果其父节点也是红的，则需要做再平衡处理，保持树的相对平衡.
节点定义
struct k_rbtree_node_t {
unsigned long rbt_parent_color;
struct k_rbtree_node_t *rbt_right;
struct k_rbtree_node_t *rbt_left;
} __attribute__((aligned(sizeof(long))));
每个节点包含三个数据：
父节点指针和颜色值，指针四字节对齐，最低bit用于表示颜色，0代表红，1代表黑；
另外两个是左右子节点指针。
主要接口
找回包含node的父对象：
page = k_rbtree_entry(node, flash_page_t, rb_node);
挂载化叶子节点，标记为红色（最低bit为0）：
k_rbtree_link_node(&node->rb_node, parent, link);
插入颜色，如有必要旋转子树，保持树平衡：
k_rbtree_insert_color(&node->rb_node, &c->root);
删除一个节点：
k_rbtree_erase(&tmp->rb_node, &c->root);
查找
while (node)
{
page = k_rbtree_entry(node, flash_page_t, rb_node);
int r = compare(address, page->address);
if (r < 0)
node = node->rbt_left;
else if (r > 0)
node = node->rbt_right;
else
break;
}
插入
struct k_rbtree_node_t **link = &c->root.rbt_node;
struct k_rbtree_node_t *parent = NULL;
while (*link)
{
flash_page_t *tmp_page;
int r;
parent = *link;
tmp_page = k_rbtree_entry(*link, flash_page_t, rb_node);
r = compare(address, tmp_page->address);
link = (r < 0) ? &(*link)->rbt_left : &(*link)->rbt_right;
}
...
k_rbtree_link_node(&node->rb_node, parent, link);
k_rbtree_insert_color(&node->rb_node, &c->root);
平衡处理
每次插入新节点，需要做平衡检测，如果不平衡，则通过旋转解决。
旋转
旋转是保持二叉树平衡的基本方法；
网上很多平衡二叉树的原理讲解，可以作为参考。
平衡二叉树的叶子节点深度差不能大于1；
旋转根据父节点和当前节点所在位置可以分为四种情况：LL, LR, RL, RR.
LL型：以被破坏节点为基础进行右旋处理。
RR型：以被破坏节点为基础进行左旋处理。
LR型：以被破坏节点的左节点为基础先进行一次左旋，再以被破坏节点为基础进行右旋处理。
RL型：以被破坏节点的右节点为基础先进行一次右旋，再以被破坏节点为基础进行左旋处理。
参考：
https://blog.csdn.net/m0_37914588/article/details/103754959
红黑树并不最求二叉树的极致平衡，通过红黑节点的约束规则可以通过简单的旋转实现相对均衡的平衡。
插入再平衡过程简述如下：
获取父节点，进入**循环检测起点**：
如果其父节点为空，则当前节点就是root，直接标记黑，退出循环；
如果父节点为黑，说明已经平衡，退出循环；
获取祖父节点，（父节点为红，说明其非root节点，祖父节点一定存在）；
进一步获取uncle节点，uncle节点可能是左节点，也可能是右节点，位置不同，旋转方式不同，下面只描述uncle为右节点的情况：
如果uncle不空而且为红，则将parent和uncle都标记为黑；更新当前节点为祖父节点，然后将当前节点标记为红，返回循环检测起点。
如果uncle空或者其为黑，则说明平衡破坏点已经找到，则进一步查看当前节点是否为右节点；
如果是右节点，因为parent是左节点，而且是red，所以是LR型，先做一个旋转，变成LL型；
最后做一次LL型旋转，退出循环；
parent是右节点的情况类似，只是判断方向相反。
虽然两个分支代码流程非常相似，但是很难复用。
总结：红黑树恢复平衡过程就是找出连续的红节点，然后根据节点所在位置类型做旋转来达到相对平衡状态。
删除
删除过程比插入复杂。分为erase和rebalance两个过程。
erase有三种子节点存在状态需要处理，L/R/LR，继而根据子节点的子节点状态确定是否需要进行rebalance。
rebalance和插入节点后的颜色标记过程相似，会用到同样的旋转操作。
