This week task consisted of analysis present hashing scheme and coding style in the linux XIA source code. I have will be writing a brief description of the concept i understood. The functions defined int the source code resembles analogously to 3 primitive function in hashing
INSERT , DELETE , LOOKUP
##insert
###vxidty.c
location of file : net/xia/vxidty.c
Use of file : to insert and delete xid_type from table mapping
Functions Used : there two main Functions in this file
####Description
int vxt_register_xidty(xid_type_t ty)
:
This function inserts the xid_type in to the form old map to the new map. to understand how it works we will understand the currunt code step by step.
```c
int vxt_register_xidty(xid_type_t ty)
{
struct xip_vxt_entry *entry, *old_map, *new_map;
int ret;
mutex_lock(&vxt_mutex); ``` entry point for old_map and new_map are defined. `ret` is the return value RETURN
-EEXIST if @ty is already registered.
-EINVAL if @ty can't be allocated at this time due to the mapping mechanism's limitations.
-ENOSPC if the mapping is full.
The index allocated to @ty, that is, a number greater or equal to zero.
mutex_lock lock is bucket structure is used to maintain a lock in a concurrent environment when different threads try to add or remove from the same location.
c
/* Check that everything is ready. */
old_map = writable_current_map(); /* get_entry_locked() requires it. */
entry = get_entry_locked(old_map, ty);
if (entry->xid_type == ty) {
ret = -EEXIST;
goto out;
} else if (entry->xid_type) {
ret = -EINVAL;
goto out;
}
ret = find_first_zero_bit(allocated_vxt, XIP_MAX_XID_TYPES);
if (ret >= XIP_MAX_XID_TYPES) {
ret = -ENOSPC;
goto out;
}
checking if everything is ready and all the map corresponds to a valid xid_type format. If not abort the process. Value of the xid_type @ty as well as the a acceptable ret value is checked.
It follows a locking mechanism which prevents function from operating on same memory space simultaneously hence providing a lock key mechanism for operation.
```c
/* Cook a new map. */
__set_bit(ret, allocated_vxt);
new_map = next_map();
memmove(new_map, old_map, MAP_SIZE_IN_BYTE);
entry = get_entry_locked(new_map, ty);
entry->xid_type = ty;
entry->index = ret;
/* Publish the new map. */
rcu_assign_pointer(xip_virtual_xid_types, new_map);
synchronize_rcu(); ``` As previously explained lock and key mechanism used on the maps, this section act as a critical section to the function. a `new_map` is initialized and then an `entry` point is made which act as a head of the hopscotch map. entry values are filled with @ty data and a index value ret.
c
out:
mutex_unlock(&vxt_mutex);
return ret;
}
Aborted signal go to this line for execution. mutex_unlockunlocks the previously locked mutex and then returns ret value.
int vxt_unregister_xidty(xid_type_t ty) follows similar process but the main difference lies in one line code which replaces the entry values with 0 as a default value. this indicated the the value @ty has been removed from the new_map.
```c int vxt_unregister_xidty(xid_type_t ty) { struct xip_vxt_entry *entry, *old_map, *new_map; int ret;
mutex_lock(&vxt_mutex);
/* Check that everything is ready. */
old_map = writable_current_map(); /* get_entry_locked() requires it. */
entry = get_entry_locked(old_map, ty);
if (entry->xid_type != ty) {
ret = -EINVAL;
goto out;
}
ret = 0;
/* Cook a new map. */
BUG_ON(!__test_and_clear_bit(entry->index, allocated_vxt));
new_map = next_map();
memmove(new_map, old_map, MAP_SIZE_IN_BYTE);
entry = get_entry_locked(new_map, ty);
memset(entry, 0, sizeof(*entry));
/* Publish the new map. */
rcu_assign_pointer(xip_virtual_xid_types, new_map);
synchronize_rcu();
out: mutex_unlock(&vxt_mutex); return ret; } ```
header file which contains function definitions of xt_to_vxt() and xt_to_vxt_rcu()
#lookup
```c #ifndef _NET_XIA_VXIDTY #define _NET_XIA_VXIDTY
/* * XID types are 32 bits long, so one cannot just map them to something else * using an array like IPv4/IPv6 can do with its protocol/next-header field. * Nevertheless, having an efficient way to map XID types to other * data structures is important for an XIA stack. * * Given that an XIA stack is expected to support only a small number of * principals at the same time, a hardware solution would be to use * a small Content-Addressable Memory (CAM) to map XID types to * sequential integers, which, in turn, allows direct maps with arrays. * * The code in this file emulates that hardware solution using perfect hashing. */
/* It must be a power of 2. */ #define XIP_VXT_TABLE_SIZE 64
/* Virtual XID Type */
struct xip_vxt_entry {
xid_type_t xid_type;
int index;
};
```
defining the structure of xid_type and declaring the table size to 64
c
extern const struct xip_vxt_entry *xip_virtual_xid_types;
```c /* Convert XID type to its Virtual XID Type. * * IMPORTANT * Only call this function holding an RCU reading lock; * otherwise call xt_to_vxt(). * * RETURN * The index allocated to @ty, a number greater or equal to zero, * if @ty is mapped. * Otherwise -1. */ static inline int xt_to_vxt_rcu(xid_type_t ty) { if (likely(ty > 0)) { const struct xip_vxt_entry *entry = &( rcu_dereference(xip_virtual_xid_types) [__be32_to_cpu(ty) & (XIP_VXT_TABLE_SIZE - 1)] ); if (likely(entry->xid_type == ty)) return entry->index; } return -1; }
/* NOTE: if RCU reading lock is held, consider calling xt_to_vxt_rcu(). */ static inline int xt_to_vxt(xid_type_t ty) { int ret;
rcu_read_lock();
ret = xt_to_vxt_rcu(ty);
rcu_read_unlock();
return ret; }
/* Register @ty among virtual XID types. * * IMPORTANT * This function may sleep. * * RETURN * -EEXIST if @ty is already registered. * -EINVAL if @ty can’t be allocated at this time due to the mapping * mechanism’s limitations. * -ENOSPC if the mapping is full. * The index allocated to @ty, that is, a number greater or equal to zero. */ int vxt_register_xidty(xid_type_t ty);
/* Unregister @ty among virtual XID types. * * IMPORTANT * This function may sleep. * * RETURN * -EINVAL if @ty is not registered. * Zero on success. */ int vxt_unregister_xidty(xid_type_t ty);
```
04 August 2015