DLIST hack (cont.)

Last blog was about a doubly circular linked list, as well as some common definitions. This article is going to talk about why a generic doubly circular linked list is useful. The main reason to use the DLIST structure mentioned in the previous article is because it is very generic. Otherwise you will have next/prev self-referential structure pointers. In this case, we made a struct whose sole members were self-referential structure pointers. Therefore, if any struct has this structure as a member, then it can link to any other struct that also has this same structure as a member.

This is a little bit odd, but useful. The oddity is the reason why it's a _hack_. To see why this would be useful is easy. You can chain multiple different types of structures. This is quite amazing actually, and there is a way to get the original structure that holds this DLIST object within it.

Before giving an example, I will describe a way, in which we can get the original structure whose DLIST member is being chained within the doubly cirucluar linked list. There is another post, in which I described the list-head problem. Whereby, if you have an element within a structure, you can go to the top of the structure if you know how many bytes the top of the structure is in regards to the actual element of the structure. All you need to do is subtract the bytes from the starting address of the element within the structure and the offset position of the element within the structure definition.

Let's see some code:

typedef struct dlist {
        struct dlist * next;
        struct dlist * prev;
} dlist_t;

typedef struct A {
        int c;
        dlist_t list;
        int a;
} A_t;

#define DLIST_INIT(dlistp) \
{ \
        (dlistp)->prev = (dlistp)->next = (dlistp); \
}
#define DLIST_ADD2HEAD(dlistp, newp) \
{ \
        dlist_t *oldfirstp; \
        oldfirstp = (dlistp)->next; \
        oldfirstp->prev = (dlistp)->prev; \
        (newp)->next = oldfirstp; \
        (newp)->prev = (dlistp); \
        (dlistp)->next = (newp); \
}
#define DLIST_ADD2TAIL(dlistp, newp) \
{ \
        dlist_t *oldlastp; \
        oldlastp = (dlistp)->prev; \
        (dlistp)->prev = (newp); \
        (newp)->next = (dlistp); \
        (newp)->prev = oldlastp; \
        oldlastp->next = (newp); \
}
#define DLIST_GET_ELEMENT(ptr, type, element_of_type) \
        ((type *)((char *)(ptr) - (size_t)offsetof(type, element_of_type)))

int main() {

        A_t a1, b1, c1;
        a1.a = 3, b1.a = 4, c1.a = 5;

        DLIST_INIT(&a1.list)
        DLIST_INIT(&b1.list)
        DLIST_INIT(&c1.list)

        DLIST_ADD2TAIL(&a1.list, &b1.list)
        DLIST_ADD2TAIL(&a1.list, &c1.list)

        printf("%d\n", DLIST_GET_ELEMENT(&a1.list, struct A, list)->a);
        printf("%d\n", DLIST_GET_ELEMENT(a1.list.next, A_t, list)->a);
        printf("%d\n", DLIST_GET_ELEMENT(a1.list.prev, A_t, list)->a);
        printf("%d\n", (unsigned)(&((A_t *)0)->list));

        return 0;
}

This allows us to chain any structure that has a DLIST member somewhere located within the structure.

DLIST hack

DLIST stands for doubly-circular linked list.

These are defined as follows:

        -------
prev<-- |     | -->next
        -------

They actually point back to themselves, initially.

typedef struct dlist {
   struct dlist * next;
   struct dlist * prev;
} dlist_t;

Some key defines: (dlist is a structure, and newNode is a structure *)

#define DLIST_INIT(dlist) \
   (dlist).next = &(dlist), \
   (dlist).prev = &(dlist)

#define DLIST_ADD2TAIL(dlist,newNode) \
   (newNode)->next = &(dlist), \
   (newNode)->prev = (dlist).prev, \
   (dlist).prev->next = (newNode), \
   (dlist).prev = (newNode);

// Assumes the first element is actually
// dlist.next
#define DLIST_REMOVE_FROM_HEAD(dlist) \
   (dlist).next = (dlist).next->next, \
   (dlist).next->prev = &(dlist);

#define DLIST_REMOVE_FROM_TAIL(dlist) \
   (dlist).prev->prev->next = &(dlist), \
   (dlist).prev = (dlist).prev->prev;

#define DLIST_ADD2HEAD(dlist,newNode) \
   (newNode)->next = (dlist).next, \
   (newNode)->prev = &(dlist), \
   (dlist).next->prev = (newNode), \
   (dlist).next = (newNode);

#define DLIST_ELEMENT(dlist,type,element) \
   ((type *)((char *)&(dlist) - (size_t)offsetof(type,element)))

Buddy Memory Allocator

Buddy Memory Allocator

This is a simple memory allocator to design. Lots of internal fragmentation goes on, but the design is fairly simple. First off, when designing a memory allocator, basic essentials are understood as common sense knowledge.

Arena's are big memory "chunks" given to a user level process for dynamic memory allocation usage. Within each arena, there are fragments. Each arena manages its own
fragments that are allocated to the user. Also, above that, the memory allocator will license a memory fragment from any free memory segment >= to the fragment asked. Also, for alignment issues, the fragment asked will be the next highest byte-alignment for easy transaction. There are minimum and maximum memory allocation requests.

Also, the buddy memory allocation schema is used when freeing up memory allocations, and then coalescing fragments together to form the original allocation units. Also, when you coalesce two "buddies" together, they have to be of the same size (for easy manipulation). There are certain issues that the buddy memory allocator I have been studying does. It allocates the largest chunk first, and then goes down by powers of 2 until you run out of memory in the arena (also, note that no fragment size will be less than the minimum memory allocation unit defined).

With that in mind, the arena needs to know which fragments are being allocated and freed. Also, we need each fragment to know which arena it belongs to. There is an option also, to include an array of linked lists depending on the size of the allocation that it can perform. Also, there is the necessity of figuring out who the buddy of one fragment is. This is essential since we let each fragment have only one buddy. Therefore, the main target is to identify fragments->Arena and Arena->fragments relationships. Each fragment can have an identifier detailing the bitmap of the arena, and each arena could have a mapping detailing which allocations are free or not.

Therefore, here are a couple of attributes:

#define GET_BUDDY(arena,fragment,lg2size) \
   ((typeof(fragment))((char *)arena + 
               (((size_t)((char *)fragment - (char*)arena)) 
                 ^ (1<<(lg2size))))

typedef struct bitmap {
   uint32_t arenaKey1;
   uchar_t  bitset[TOTAL_FRAGMENTS / CHAR_BIT];
   uint32_t arenaKey2;
} bitmap_t;

typedef struct fragment {
   bitmap_t * arenaId;
   /* some fragment header info */
   uint32_t log2size;
} fragment_t;

/* Holds all fragment header's of a certain size, 
   and holds the fragment header's of all sizes. */
fragment_header_info * fragHeaders[N_ALLOCATION_SIZES];

Linux Kernel Code: #define for loop

When competing in algorithm-type competitions, there tends to be a need for looping through structures. The infamous #define for loop comes to mind. Nearly all TC competitors use it, but the originality was unknown -- well, until a couple of days ago. Here I am studying on Linux Kernal Internals, and I come to what seems to be either a macro or an inline function:

   for_each_task(p)

This segment of code is used a lot in the Linux Kernel. First and foremost, there is no notion of thread or process within the linux kernel. The single most basic unit idea of a transaction is a task. Therefore, the Linux Kernel has a table of tasks. Before, the Linux Kernel 2.4, the Linux Kernel would have a table or an array of task structures. Not anymore, it is constructed so that it holds a doubly circular linked list of tasks. Furthermore, the first task that gets inserted into this list is the kernel initialization. Therefore, it's name is such as "init_task" and so when you get back to this address, you know you have cycled around. Also, there is a notion of current -- the current task. Back to the point, since it is now a doubly circular linked list structure, the for_each_task(p) is defined as the following:

#define for_each_task(p) \
   for (p = &init_task; (p = p->next_task) != &init_task; )

This is the first place where a #define is used where a for-loop is constructed. Therefore, many programmers nowadays use a #define in low-level systems programming. It's nothing new; it's been used since all kernel eternity...

FFS: Revisited (How to find the first bit set)

This seems to be a reoccurring problem that's looked at within this blog. Moreover, it has many features that are good to learn from. This article will focus on the binary-search with the respect of the number of bits.

This is a classic binary search problem, with the bits as the search space, and the conditional expression will be if the mask & (bitwise-AND) bits_val == 0 or not.

Analysis:
If we separate an uint32_t into 2 16-bit segments, then a branch would be if the lower end or higher end held the first bit (0). And then branch with 2 8-bit segments, etc.
This is quite easy to see; the only stipulation is that we need to keep a running counter when we need to skip "bits". Also, in this case, we will always consider the low-end order since it will be more intuitive.

Therefore, if the bits_val & mask == 0, we need to count all those bits + shift the original bits_val by that number of bits, since we are accounting for it to be on the low-end order.

The algorithm therefore looks like so:

#define BITS 32
uint32_t ffs(uint32_t bits_val)
{
   uint32_t offset = 0;
   uint32_t mask = (1<<(BITS / 2)) - 1, nbits = BITS / 2;
   do {
      if ( (bits_val&mask) == 0) {
         // update offset and low-end order of bits_val
         offset += nbits;
         bits_val >>= nbits;
      }
      // update the bits used as well as the new mask.
      nbits /= 2;
      mask >>= nbits;
   } while(nbits);
   return (offset);
}

uint32_t fls(uint32_t bits_val)
{
   uint32_t offset = BITS-1;
   uint32_t nbits = BITS / 2, 
            mask = (((1<<(BITS/2))-1)<<(BITS/2);

   do {
      if ((bits_val&mask) == 0) {
         offset -= nbits;
         bits_val <<= nbits;
      }
      nbits /= 2;
      mask <<= nbits;
   } while(nbits);
   return (offset);   
}

Also, as a side note, there are many problems that deal with byte-alignment.
Another proposed solution, is the following:
(uses a math trick to get the dividend within range and multiply with the alignment)

#define ALIGN(x,align) ( (((x)+(align)-1)/(align)) * (align) )

Since it uses integer division, (x + align - 1)/align will give you the value that is within range, since x could be a multiple of "align," it will give you the low(ceiling) order of x + align - 1. When multiplying this by align, it will yield the exact (next) multiple of align >= x.

Automated daily jobs

On *nix machines, there's something called cron. It's very helpful for doing daily builds for testing purposes. Actually, it's good for anything that needs to be run by automation. Test automation, build automation, scheduled tasks, ibid et al.

The whole deal with cron jobs are that you have crontabs, where a crontab is a file that describes when it should be run, where mail should be sent to in case of output or errors. It will pinpoint the minute, hour, day of week, month, and the like. Also you give the script or command to automate. To see a more definitive description, check the man pages.

This makes your life a lot easier.

Life: Up to Date

Well, it seems I haven't written in a few weeks. I have been real busy and needing to make decisions. However, none of them are good.

#1) I dropped out of the master's program at UWF.
#2) I am more than behind in deadlines at work.
#3) I am more behind in my studies.
#4) I am behind in studying for the GRE/LSAT.
#5) I have made a decision to study with a CMU alum, to get back into the game.

Therefore, I need to do things that counter-balance my bad decisions.
My study plan goes as follows:
1) LSAT
2) GRE (Maths/Verbal)
3) Technologies (awk, sed, rss feeds, bash/ksh, php, C/C++)
4) Back-end Development (C/C++)
5) Datastructures/Algorithms
6) Projects - Game Programming
7) General Reading.

A situation that is indeed funny to behold. The reason for me dropping out hinges upon two facts that are pretty bold for me to say, but I believe they are true.
1. Dr. Coffey scored me an F and didn't respond with any emails or notification of my grade as an F.
2. Dr. Edwards is the most slack professor/advisor at the university.
Wisdom is not wisdom when it's brutally demeanored by slack individuals; it then just proceeds to be laziness with experience. Therefore, it's time to pick up the slack. Dropping out of school was the wisest choice I have ever made, and it just pushes me to strive even harder. (Plus, the topics I was studying was not what I need to be concentrated on)

-- some pathetic coder