u-boot中环境变量操作和hash表

u-boot对环境变量的处理主要包括两部份：
1是环境变量初始化，2是环境变量的设定、删除等操作。下面将分别进行讨论。
这里所使用的u-boot版本为2015.7，硬件为I.MX6 boundary nitrogen6q开发平台。
1 .环境变量初始化
1.读取环境变量
环境变量的初始化在board_init_f阶段完成，其由在common/barod_r.c中定义的静态函数initr_env来实现：

should_load_env是board_r.c中的静态函数，经过编译预处理，直接返回1。接着履行env_relocate()，该函数在common/env_common.c中实现，编译预处理后为：

gd->env_valid在board_f阶段中的函数env_init调用中被赋值为1，这里将接着履行env_relocate_spec。env_relocate_spec针对不同的环境变量存储装备有多处实现，这里使用CONFIG_ENV_IS_IN_SPI_FLASH宏，所以使用common/Env_sf.c中的定义（参见common/Makefile），由于没有定义CONFIG_ENV_OFFSET_REDUND，则
env_relocate_spec实现为：
如果从spi flash中读取环境变量成功，则调用函数env_import，该函数将对读取到的环境变量进行CRC校验，如校验失败，会履行set_default_env。否则接着调用himport_r履行hash表的初始化。
set_default_env函数用来配置默许的的环境变量。它在common/env_common.c中实现:
default_environment为include/Env_default.h中定义的变量。它是1个常量字符串数组。在default_environment定义时赋值时，赋值的常量字符串又包括了nitrogen6x.h中的宏定义CONFIG_EXTRA_ENV_SETTINGS，该宏定义为代表附加环境变量的常量字符串。也即是default_environment值为Env_default.h加上nitrogen6x.h文件中定义的环境变量值。
另外注意，set_default_env函数中，gd->flags最后被赋值为gd->flags |= GD_FLG_ENV_READY，而从SPI Flash中读取的环境变量，在使用后续函数env_import时，该函数在返回前也会进行一样的赋值操作。该标志代表环境变量已准备好，可以对其进行打印、编辑操作。
环境变量读取的履行总流程图示以下：


不管是使用默许的环境变量，还是使用从spi flash读取到的有效环境变量配置，完成环境变量的读取后，都将调用himport_r将获得到的环境变量导入到hash表中。
2. 导入环境变量到hash表中
u-boot中使用3个结构体描写了hash表，它们在include/search.h文件中定义:
struct hsearch_data;
struct _ENTRY;
struct entry，即ENTRY;
下图描写了这些结构体的定义和它们之间的关系：

struct _ENTRY代表1个hash表项，其内部包括的struct entry(ENTRY)为hash表中具体的内容数据。struct hsearch_data用来管理全部hash表。struct _ENTRY结构体中的成员used也是作为hash表的管理之用。
读入的环境变量会导入到hash表中，以方便环境变量的查找，插入，编辑等操作。
在下面的描写中，使用了hash表键值和key两个名称，hash表键值代表上图中的hash表项索引index(整数)，它还会存储在struct _ENTRY成员变量used中，当其为空时，表示该hash表中该索引表项未被占用；key代表是的是上图中ENTRY结构体中的成员变量字串指针key。hash表键值根据key通过hash算法来生成。key在u-boot中实际代表是环境变量名(name)。ENTRY结构体中的成员变量字符串指针data则代表相应环境变量的值(value)。

环境变量的hash表导入是通过函数himport_r来实现。该函数包括代码较多，为了便于分析，这里删除略去了出错检查和复杂的字符串操作代码，只保存其主要架构：

该函数首先为环境变量分配内存空间。如果标志参数flag中包括H_NOCLEAR---该标志代表强迫清除hash表，那末就调用hdestroy_r函数。如果hash表为空(!htab->table)那末将创建hash表。语句
CONFIG_ENV_MIN_ENTRIES + size / 8
用来根据环境变量包括的字节数，和CONFIG_ENV_MIN_ENTRIES宏定义的最小表项数，来计算hash表包括的表项数。这里的8，使用的是估算法，假定每条环境变量占用8个字节，即key=value(不含等号)。源代码中对此有详细注解。然后调用hcreate_r创建hash表----初始化htab->size为上面的表项数，分配hash表的内存空间。
if(crlf_is_lf)代码段处理环境变量中包括的'\r'。上面程序中有详细注解。
do {
...          
} while ((dp < data + size) && *dp); 
do-while代码段解析环境变量，然后将解析后的所有环境变量，逐条填入hash表中。程序首先解析环境变量，每条环境变量的设定用"\0"分割，环境变量名和其设定值用"="号分隔，程序最后将解析后的环境变量名存入name，值存入value中，如"baudrate=" "115200" "\0"，解析后name的值为"baudrate",value的内容为"115200"。
e.key = name;
e.data = value;
hsearch_r(e, ENTER, &rv, htab, flag);
上述代码将环境变量名字符串name赋值给hash表项中的key，环境变量值赋值给hash表项中的data，然后将e代表的hash表项插入到hash表中。下面将会分析具体的插入操作实现。
3.环境变量hash表的插入、编辑等操作
下面的讨论触及到hash表键值生成算法，关于这方面的内容，可参见数据结构的相干书籍和网络上的相干文章。
u-boot中触及到的hash表操作主要包括环境变量初始化和环境变量编辑。前者被上面的函数himport_r调用，后者则被u-boot1些环境变量编辑命令所调用。

这些操作主要通过函数hsearch_r来实现。删除操作则通过hdelete_r函数实现。

和通用的hash表操作不同，u-boot中hash表的操作中附加了权限检查和可履行的回调函数。前者是针对结构体ENTRY中的成员flags的检查，后者则是对ENTRY中的成员callback的调用。

下面主要分析hash表项初始化(插入表项，和编辑操作中的插入相同)和编辑(插入、修改，删除等)操作的实现函数hsearch_r。我们将分段讨论该函数。

代码段1：hash表键值生成算法
其中的代码
是hash键值算法的核心。将item.key---环境变量name中的字符移位并累加，然后模hash表项数，即为该环境变量在hash表项中的数组索引---hash表键值。注意这里使用的还是估算法，即假定每条环境变量字符串占用8个字节，注意上述代码中hval为32位数，移位操作8次就会产生循环。
保存了表项数组索引0的空间，在上面himport_r调用的hcreate_r分配hash存储空间时，多分配了1个表项空间，即该处的保存空间。
代码段2：hash表键值重复冲突处理和编辑操作
上述代码中
别处使用的函数_hdelete中会把used填充为⑴，变量first_deleted记录第1次被删除的键值。下面的代码段3将会使用此处被赋值的first_deleted。
函数_compare_and_overwrite_entry主要履行3项操作：
c.1)检查以idx为索引的hash表项中的key(环境变量名字符串)是不是和输入参数item.key1致，不1致返回⑴
c.2)调用change_ok履行权限检查，不通过返回0。

c.3)如果相应表项的成员callback 不为空，则履行该回调函数。函数履行失败返回0。

      回调函数在hash表项初始化时或被填充（见下面的代码段3）。

c.4)履行hash表项修改操作，即修改hash表项中的data为新值。
htab->table[idx].used的包括的值及其含义说明以下：
0        -- 未使用；
⑴      -- 曾被删除   
index -- 键值索引
当htab->table[idx].used为0时，则代表还未被使用和填充，将跳过代码段2，履行代码段3。
当htab->table[idx].used不为空，表示以下3种情况：
a)代码段生成的hash表键值出现重复
即以idx为索引的表项已被其他环境变量占用，由于环境变量名是唯1的，那末_compare_and_overwrite_entry履行的hash表项中key(代表被占用的环境变量名)和输入参数item.key1致性检查将出错返回⑴。然后调剂hash表的键值生成算法，履行while循环，直至找到1个未重复的hash表键值，注意while将循环里重复上述检查进程。

另外还有1种情况，即此时hash表项中key为空，即还未被初始化，那末_compare_and_overwrite_entry也将返回⑴。

这里重点说明的是hash表项初始化中键值生成时重复问题，但键值重复的处理又不但限于此。环境变量编辑时所触及的hash表操作也会遇到该问题。但后者只不太重复还原前者的键值生成操作流程，以保证键值映照的1致性。

b)已被使用，这里是编辑操作
_compare_and_overwrite_entry也会检查根据代码段1键值算法映照的键值是不是重复，如果不重复，那末履行上述的_compare_and_overwrite_entry中的c.2和c.3操作。c.2和c.3操作如出错均会返回0，接着履行c.4完成表项内容修改操作（修改环境变量的值value)，出错也将返回0。所以上面的操作出错都会返回0，而非⑴，则表示编辑操作完成，
hsearch_r函数直接返回。
如果_compare_and_overwrite_entry返回⑴, 表示该hash表项初始化时，在hash表生成时的键值处理中，已有重复键值。所以，针对已被初始化的hash表，这里也要处理对这类重复键值进行重定位。即履行上述的a)。由于第1个被删除的hash表项即为有效的键值。
c.)相应的hash表项曾被删除，这里再次被使用
如果已被删除，那末只有针对hash表项的再次初始化才成心义，编辑操作履行_compare_and_overwrite_entry中的c.1返回⑴，接着将履行a)。其实，此时期码再次履行a)要末没法找到有效的表项索引。即便能找到，下面的代码段3也只会使用第1次的曾被删除的表项索引值，该值记录在first_deleted中。
从上面的分析中可以看出，函数_compare_and_overwrite_entry的返回值为⑴时，将hash表项初始化时和编辑操作时的键值重复检查混淆处理，致使程序履行流程复杂化。所以该函数的首字符为下划线，表示可疑版本(可改进)。

代码段3：
这里主要履行的是hash表项的初始化，在u-boot中使用新增环境命令时也将履行该段代码。其他环境变量的编辑命令1般在代码段2都被正确履行后直接返回。而在使用u-boot命令setenv xxx新增1个环境变量时，代码段2也没法正确履行，不能返回到上层函数。
不管是全部hash表项的初始化，还是上述新增环境变量时的插入新的hash表项，它们履行的操作都是相同的，即都是插入新表项操作。程序履行到代码段3时，上面的程序已生成了有效的hash表键值，并赋值给变量idx。
htab->filled代表已使用的hash表项数，如其值大于hash->size，即hash表项数，那末设置毛病标志，并直接返回0。
如果first_deleted不为空，则其在代码2中曾被赋值，表示该表项曾被删除过，其first_deleted代表第1个被删除的表项对应的键值。

上面的代码完成hash表项内容的填充。strdup函数会分配内存空间，注意entry.key和entry.data都是指针变量。if语句履行键值1致性检查。填充无毛病则变量htab->filled递增1，该变量上面使用过，代表已使用的hash表项数。接着履行函数env_callback_init和env_flags_init，前者是hash表项中回调函数的初始化，后者是hash表项中flags的初始化，flags用来标志访问权限。这两个函数的实现比较复杂，会另做1节对它们分析。接着的代码：
htab->change_ok函数在其定义时赋值为env_flags_validate，这里不为空，则将调用该函数履行操作权限检查。
代码：履行在env_callback_init中初始化的回调函数。如权限检查和回调函数的履行出现毛病，则直接删除该hash表项。
这里，可以看到，环境变量在其初始化的hash表填充时，就会调用表项中设置的回调函数。例如，有以下的存储在spi flash中的环境变量：以第2行的环境变量"stdout=" "serial,vga"为例，当其从spi flash加载到内存空间中，并填充到hash表中时，如果该项环境变量的相干赋值（创建）操作被允许（权限检查通过），且有相应的回调函数，那末此处就会履行该函数。另外代码段2中的_compare_and_overwrite_entry中也将履行权限检查和回调函数。如，在u-boot中履行：
=>setenv stdout serial,hdmi
那末该命令会调用do_env_set函数，它又调用上述的hsearch_r并履行代码段2。所以，在"console_init_r分析"1节中，曾提到过该命令是立即生效的。
3.env_flags_init和env_callback_init
env_flags_init初始化操作权限，env_callback_init初始化回调函数。
所谓的权限是针对每个hash表项而言的，而每个hash表项对应1条环境变量，权限即环境变量的创建，修改，删除等权限。回调函数是履行这些环境变量的操作后附加的1些操作。
如上面的例子中，履行setenv stdout serial,hdmi时，会首先检查环境变量stdout的修改操作是不是被允许，如果允许将环境变量的值修改成serial,hdmi，然后调用回调函数，重设console。

下面来逐1分析这两个函数的具体实现。

3.1 env_flags_init

权限操作集中在文件env_flags.c中：

first_call为静态变量，其定义时初始化为1。上述代码首先从环境变量中获得flags的值（ENV_FLAGS_VAR），然后调用env_flags_lookup：1般地，环境变量中不含ENV_FLAGS_VAR，那末此处的flags_list值为空，则履行env_attr_lookup(ENV_FLAGS_LIST_STATIC, name, flags);
ENV_FLAGS_LIST_STATIC定义为：每条环境变量的操作权限用逗号分隔，变量名和权限位使用冒号分隔。如上面ipaddr是环境变量名，i是权限描写。
权限描写又分为权限类型和权限值描写。

类型即是该环境变量对应值的类型，其字符的定义实现及其含义以下：
字符s代表string类型数据
字符d代表decimal类型数据
字符x代表hyexadecimal类型数据
字符b代表boolean 类型数据
字符i代表ip address 类型数据
权限值及其含义以下：
字符a表示any，可进行任何操作，它为权限的默许值
字符r表示read-only,只读
字符o表示write-once，可1次写
字符c表示change-default，可改变成默许值
上述权限值对应的u-boot操作包括在env_flags_varaccess_mask变量中：

env_flags_init函数会调用函数env_parse_flags_to_bin，将权限值字符，映照为上面env_flags_varaccess_mask变量中的2进制值，即

字符a终究映照为0
字符r映照为：ENV_FLAGS_VARACCESS_PREVENT_DELETE |
            ENV_FLAGS_VARACCESS_PREVENT_CREATE |
            ENV_FLAGS_VARACCESS_PREVENT_OVERWR,
字符o映照为:
ENV_FLAGS_VARACCESS_PREVENT_DELETE |
            ENV_FLAGS_VARACCESS_PREVENT_OVERWR,
字符c映照为：
 ENV_FLAGS_VARACCESS_PREVENT_DELETE |
            ENV_FLAGS_VARACCESS_PREVENT_NONDEF_OVERWR
从上面的ENV_FLAGS_VARACCESS_XX宏定义名可以看出其代表的操作权限。

env_flags_init最后会将映照后的2进制权限位值赋值给hash表项的成员flags。struct hsearch_data的成员变量change_ok，它是1个函数指针，定义时被初始化为env_flags_validate。环境变量操作的权限检查是通过该函数来履行。

如果定义了CONFIG_ENV_ACCESS_IGNORE_FORCE，则所有的访问权限将被疏忽。
针对不同的操作，传给env_flags_validate的参数op值就不同。
在上面的函数hsearch_r中，代码段2中调用_compare_and_overwrite_entry，然后调用change_ok，传入的op值是env_op_overwrite，而代码段3中，调用change_ok ，传入的op值为env_op_create。这样env_flags_validate函数将根据不同的op操作，来履行相应的权限检查。如当操作是创建hash表项时，那末，会检查ENV_FLAGS_VARACCESS_PREVENT_CREATE标志。
另外，如果相应的环境变量hash表项没有定义flags，则其值为0，允许所有的权限。即针对环境变量的操作，默许的权限为全部使能。
3.2 env_callback_init
代码首先从环境变量中获得回调函数的值（ENV_CALLBACK_VAR），然后调用env_attr_lookup，这里使用参数ENV_CALLBACK_LIST_STATIC，该宏定义以下：
每条环境变量操作的回调函数用逗号分隔，变量名和回调函数索引字符串使用冒号分隔。如上面stdin是环境变量名，冒号后面的console是回调函数索引字符串。之所以称为"回调函数索引字符串"，由于这里只是字符串，必须使用映照机制，将回调函数索引字符串和所对应的回调函数关联起来。然后使用回调函数索引字符串，查找到相应的回调函数。

结构体struct env_clbk_tbl保持着这样1个回调函数索引字符串和回调函数的映照表：

利用宏U_BOOT_ENV_CALLBACK填充该结构体，将上述的回调函数索引字符串和回调函数关联起来，如：
U_BOOT_ENV_CALLBACK(console, on_console);
将回调函数索引字符串"console"和on_console回调函数相干联，那末上述环境变量stdin操作最后的回调函数就是on_console。

在u-boot中，使用U_BOOT_ENV_CALLBACK定义并初始化的struct env_clbk_tbl变量都寄存在名为_u_boot_list_2_env_clbk_2_xx的符号段中。

U_BOOT_ENV_CALLBACK(console, on_console)预编译后为：

注意上述section中的符号段名。所有益用U_BOOT_ENV_CALLBACK 定义的的环境变量回调函数都将放在这样1个以_u_boot_list_2_env_clbk_2开头的符号段中。
在u-boot生成的符号表文件system.map中可查看到这些段：
env_callback_init函数中接着履行的find_env_callback就是在_u_boot_list_2_env_clbk_2_xx段中查找环境变量相应的符号段，该符号也即上述struct env_clbk_tbl变量的地址。find_env_callback函数对其中name进行核对后，返回有效的回调函数指针然后函数env_callback_init将其赋值给hash表项的成员callback。这样就完成了环境变量hash表项的回调函数初始化。