mems.c

新一代基于事件的嵌入式操作系统dyos在三星的s3c44b0的arm芯片上的完整移植代码

//----------------------------------------------------
//Copyright (C), 2004-2009,  lst.
//版权所有 (C), 2004-2009,   lst.
//所属模块:堆管理模块
//作者：lst
//版本：V1.0.1
//文件描述:提供块相联内存分配策略
//其他说明:
//修订历史:
//    2. 日期:2009-03-03
//       作者:lst
//       新版本号：1.0.1
//       修改说明: 修正了__m_check_memory函数的一处错误，该bug由网友sniper提交
//    1. 日期:
//       作者:
//       新版本号：
//       修改说明:
//------------------------------------------------------
#include "inc_os.h"
#include <string.h>

//字节数据前导0个数表,256字节,用于快速查寻首个非0位的位置
uint8_t const cn_leading_zero[]=
{
    8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};
//字节数据后缀0个数表,256字节,用于快速查寻首个非0位的位置
//uint8_t const cn_suffix_zero[]=
//{
//    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
//};

static struct mem_global tg_mem_global;
static struct mutex_LCB tg_mem_mutex;   //保护tg_mem_global不被并发访问
const ucpu_t cn_low_xbit_msk_exp2 []=
{
    cn_low_1bit_1,
    cn_low_2bit_1,
    cn_low_4bit_1,
    cn_low_8bit_1,
    cn_low_16bit_1,
    cn_allbit_1,
};

const ucpu_t cn_low_xbit_msk []=
{
    0,
    cn_low_1bit_1,
    cn_low_2bit_1,
    cn_low_3bit_1,
    cn_low_4bit_1,
    cn_low_5bit_1,
    cn_low_6bit_1,
    cn_low_7bit_1,
    cn_low_8bit_1,
    cn_low_9bit_1,
    cn_low_10bit_1,
    cn_low_11bit_1,
    cn_low_12bit_1,
    cn_low_13bit_1,
    cn_low_14bit_1,
    cn_low_15bit_1,
    cn_low_16bit_1,
    cn_low_17bit_1,
    cn_low_18bit_1,
    cn_low_19bit_1,
    cn_low_20bit_1,
    cn_low_21bit_1,
    cn_low_22bit_1,
    cn_low_23bit_1,
    cn_low_24bit_1,
    cn_low_25bit_1,
    cn_low_26bit_1,
    cn_low_27bit_1,
    cn_low_28bit_1,
    cn_low_29bit_1,
    cn_low_30bit_1,
    cn_low_31bit_1,
    cn_allbit_1,
};

//----返回数组中首位1位置（前导0的个数）----------------------------------------
//功能：从数组的最高字节的最高位开始计算前导0的数量。
//参数：data,输入数组指针
//      len,数组的大小
//返回：前导0的个数
//------------------------------------------------------------------------------
ucpu_t __m_leading_zero(uint8_t *data,uint8_t len)
{
    uint8_t u8_i;
    ucpu_t  uc_j=0;
    u8_i=len-1;
    do
    {
        if(cn_leading_zero[data[u8_i]] != 8)
        {
            uc_j+=cn_leading_zero[data[u8_i]];
            break;
        }else
            uc_j +=8;
    }while(u8_i-- !=0);
    return uc_j;
}

//----计算控制表所需的字节数---------------------------------------------------
//功能：计算控制表所需的字节数
//参数：u32_pages,内存页数
//返回：字节数
//注意: 保持函数功能的单一性,不要同时计算控制结构各部分的字节数
//      移植关键:本函数与你的机器的对齐方式有关,移植时你必须了解机器的对齐方式.
//      本函数能满足绝大部分cpu的对齐要求,但不排除有例外.所以在移植时你最好读懂
//      本函数，然后考虑是否需要修改
//-----------------------------------------------------------------------------
uint32_t __m_calculate_expense(ptu32_t ua_pages)
{
    ptu32_t ua_bits,u32_return;
    ufast_t uf_grades,uf_grade_th;

    //计算阶数，即一共有多少种页尺寸,方法:地址长度减去ua_pages中前导0的数量就是
    //阶数,例如,ua_pages=5,最高位位置是bit2,有29个前导0，页尺寸有1,2,4页3种,阶数=3
    uf_grades=cn_point_bit-__m_leading_zero((uint8_t *)&ua_pages,sizeof(ptu32_t));

    //每页分配一个16位字记录拥有本页内存的事件的ID。
    //当分配高阶内存块时，只记录首页，free时并不清除。设置本字是为了防止在
    //事件间交叉分配和释放内存时不至于出错，但并不建议用户这样使用。
    u32_return = ua_pages<<1;
    //下一个数据域是ufast_t类型的,需要按ufast_t类型对齐.
    u32_return = (u32_return+sizeof(ufast_t)-1)&(~(sizeof(ufast_t)-1));
    //每阶还要分配一个ufast_t类型的数据,纪录本阶的级数
    u32_return += uf_grades*(sizeof(ufast_t));
    //下一个数据域是指针,需要按指针对齐
    u32_return = (u32_return +sizeof(void*) -1)&(~(sizeof(void*)-1));
    //每阶一个指针,指向位图所引表
    u32_return += uf_grades*sizeof(void*);

    for(uf_grade_th = 0; uf_grade_th < uf_grades; uf_grade_th++)
    {
        ua_bits = ua_pages>>uf_grade_th;   //计算本阶总位数
        do
        {
            ua_bits=(ua_bits+cn_cpu_bits-1)>>cn_cpu_bits_suffix_zero;
            u32_return +=ua_bits*sizeof(ucpu_t);    //该级位图字数
            u32_return+=sizeof(void*);	            //需要一个指针指向该位图首字
        }while(ua_bits>1); //直到所有级都分配完.
    }
    return u32_return;
}

//----延长内存记录表------------------------------------------------------------
//功能: 当内存记录表不够时(即pg_mem_record_free==NULL),调用本函数从内存中取1个
//      结构.如果预先分配的内存已经用完,则调用__malloc_block分配一页新的内存.
//      如果没有足够的内存可以分配,返回NULL.本函数内部调用,不开放给用户
//参数: 无
//返回: 如果成功延长,返回表头指针,否则返回NULL
//备注：调用本函数前应该保证中断被关闭。每次只取一个结构,而不是把新分配的整页
//      内存连到pg_mem_record_free表中,虽然增加了总的执行时间,但是提高了实时性.
//-----------------------------------------------------------------------------
/*
struct mem_record *__inc_record_link(void)
{
    static struct mem_record *record_free=NULL;
    struct mem_record *result;

    if(record_free==NULL)
        record_free=(struct mem_record*)__malloc_block(0);//分配1页内存用于记录
    if(record_free==NULL)   //表明没有内存可以分配
        return NULL;
    result = record_free;   //取得一个结构体
    result->next = NULL;    //初始化新节点的next指针
    record_free = record_free+1;  //指向下一个结构体
    if((cn_page_size-sizeof(struct mem_record)*(result-record_free))
            < sizeof(struct mem_record))
    {//本次分配的页已经用完.
        record_free=NULL;
    }
    return result;
}
*/

//----返回ucpu_t类数据前导0的个数----------------------------------------------
//功能：从ucpu_t类数据的最高位开始计算前导0的数量。
//参数：data,输入数
//返回：前导0的个数
//-----------------------------------------------------------------------------
ucpu_t __m_leading_ucpu_zero(ucpu_t data)
{
    uint8_t u8_i;
    ucpu_t  uc_j=0;
    u8_i=sizeof(ucpu_t)-1;
    do
    {
        if(cn_leading_zero[((uint8_t*)&data)[u8_i]] != 8)
        {
            uc_j+=cn_leading_zero[((uint8_t*)&data)[u8_i]];
            break;
        }else
            uc_j +=8;
    }while(u8_i-- !=0);
    return uc_j;
}

//----返回规格化阶-------------------------------------------------------------
//功能：把任意数据规格化为合法的内存尺寸。
//参数：size,欲分配的内存块尺寸
//返回：大于或等于size的最小的允许块尺寸的阶。
//-----------------------------------------------------------------------------
ufast_t __m_get_grade(ptu32_t size)
{
    ucpu_t  uc_temp;
    if(size<=cn_page_size)
        return 0;
    uc_temp=__m_leading_zero((uint8_t *)&size,sizeof(ptu32_t));
    if((cn_high_1bit_1>>uc_temp) != size)
    //如果size本身不是规格化的数,调整到比它大的最小允许块大小
    //否则维持size的大小,不做调整
        uc_temp--;

    //返回阶数,从0起计,即最小页尺寸前导0减块尺寸前导0.
    return (ufast_t)(cn_point_bit-1-cn_page_size_suffix_zero-uc_temp);
}

//----记录分配的内存-----------------------------------------------------------
//功能：1.把内存分配信息保存到running事件的内存分配链表里面,以备事件完成的时候
//      强制收回内存.如果分配的是全局内存,则不记录,事件完成时也不收回.
//      2.把内存分配信息保存到index_event_id表里面.index_event_id表的格式见结构
//      mem_global_t的定义.
//参数: address,分配的内存地址.
//      uf_grade_th,被分配的内存的阶号
//备注: 本函数由操作系统内部调用,内存分配链表是一个单向不循环链表,每事件一个.
//-----------------------------------------------------------------------------
/*
void __record_mem(uint8_t *address,ufast_t uf_grade_th)
{
    uint16_t *pl_id,id;
    ptu32_t  page;

    pg_mem_record_free->address=address;
    if(pg_event_running->held_memory==NULL)
    {   //如果running事件尚无申请内存记录,则把新内存连接到记录的头部.
        pg_event_running->held_memory=pg_mem_record_free;
        pg_mem_record_free = pg_mem_record_free->next;
        pg_event_running->held_memory->next = NULL;
    }else
    {   //如果running事件已经有申请内存记录,则把所有本事件申请的内存连接到
        //内存记录链表中相邻结点上.可由pg_event_running->held_memory访问
        struct mem_record *p;
        p=pg_mem_record_free;
        pg_mem_record_free = pg_mem_record_free->next;
        p->next=pg_event_running->held_memory;
        pg_event_running->held_memory=p;
    }

    //阅读以下条件句请结合mem_global_t中index_event_id成员定义的注释.
    pl_id = tg_mem_global.index_event_id;
    id = pg_event_running->event_id;
    page = (ptu32_t)(address-tg_mem_global.heap_bottom)
            >>cn_page_size_suffix_zero;
    if(uf_grade_th==0)
    {//分配1页
        pl_id[page] = id;
    }else if(uf_grade_th==1)
    {//分配2页
        pl_id[page] = -1;
        pl_id[page+1] = id;
    }else
    {   //分配多页
        pl_id[page] = -2;
        pl_id[page+1] = id;
        pl_id[page+2] = uf_grade_th;
    }

    if(pg_mem_record_free==NULL)
        pg_mem_record_free=__inc_record_link();
}
*/

//----查看并等待空闲内存----------------------------------------------------
//功能：等待队列是一个经过排序的双向循环链表,按照申请的内存量排序,小的在前,
//      当内存可用时,首先使申请量小的事件得到满足,这样可以使内存满足尽量多事件,
//      不使用优先级排序,因为实时事件是不允许使用动态分配的,所以不会影响实时性.
//参数：size,需要申请的内存尺寸
//      timeout，超时设置,单位是毫秒，cn_timeout_forever=无限等待，
//      非0值将被向上调整为cn_tick_ms的整数倍
//返回: true = 有空闲内存供分配，false = 无内存可分配
//备注: 本函数由操作系统调用,用户不能调用.
//------------------------------------------------------------------------------
bool_t __m_check_memory(ptu32_t size,uint32_t timeout)
{
    struct  event_script *event;
    uint32_t timeout_ticks,u32l_start_time,u32l_rest_time = 0;
    bool_t   wait;
    timeout_ticks = (timeout + cn_tick_ms -1)/cn_tick_ms;