w2d4: Splitting chunks

Split chunks
Tests for split chunk item for multiple vertical (i.e. decreasing k) and horizontal (increasing free list) steps.

• zero (k=0)
• one (k=1)
• two (k=2)
• one w/ multiple splits

Request chunks
The first version of the test contained the functionality for a new function, request_chunk(). Moved out the specific tests for split_chunk_item() and tested request_chunk() specifically.  It gives you an available chunk or splits blocks creating new ones as needed.

The first chunk request for k will split the A cell of k+1. The second chunk request for k must therefore split the B cell of k+1. At the moment, the chunk (containing both A and B) is returned, which the client code must check to see which cell is free.

w2d3: Computer setup.

Ported xmodmap-keymap to xkb for docking the laptop.

/usr/share/X11/xkb/rules/evdev.xml:

--- evdev.xml.original 2011-12-31 19:43:12.420620122 +0100
+++ evdev.xml 2011-12-31 19:43:11.776620137 +0100
@@ -4302,6 +4302,12 @@
             <languageList><iso639Id>swl</iso639Id></languageList>
           </configItem>
         </variant>
+        <variant>
+          <configItem>
+            <name>pworak</name>
+            <description>Swedish (Pworak)</description>
+          </configItem>
+        </variant>
       </variantList>
     </layout>
     <layout>
@@ -6322,4 +6328,4 @@
       </option>
     </group>
   </optionList>

/usr/share/X11/xkb/symbols/se:

--- se.original 2011-12-31 19:42:44.772620738 +0100
+++ se 2011-12-31 19:42:44.172620753 +0100
@@ -310,3 +310,74 @@
   key <AE09> { [ 0x110c97b, 0x110c90a, 0x110c98b, 0x110c965 ] };
   key <AE10> { [ 0x110c974, 0x110c909, 0x110c98c, 0x110c968 ] };
 };
+
+partial modifier_keys
+xkb_symbols "pworak_mods" {
+    replace key <CAPS> {  [ Control_L, Control_L ] };
+    modifier_map  Control { <CAPS> };
+
+    // Left control key = F20
+    // Caps = Control_L
+    replace key <AA00> {  [ F20 ] };
+};
+
+partial alphanumeric_keys
+xkb_symbols "pworak" {
+name[Group1]="Swedish (Pworak)";
+
+// don't include in the future
+include "se(basic)"
+include "se(pworak_mods)"
+
+    ///////////////////////////////////////
+    // ^1..90`
+    ///////////////////////////////////////
+    key <TLDE> { [   asciicircum,    onehalf,    paragraph, threequarters] };
+    key <AE04> { [         4,     dollar,   currency ] };
+    key <AE12> { [     acute,      grave,    plusminus,      notsign ] };
+
+    ///////////////////////////////////////
+    // QWERTY
+    ///////////////////////////////////////
+    key <AD01> { [     aring,      Aring,    question      ] };
+    key <AD02> { [  adiaeresis, Adiaeresis,  parenleft          ] };
+    key <AD03> { [ odiaeresis, Odiaeresis,  parenright          ] };
+    key <AD04> { [         p,          P,        thorn,        THORN ] };
+    key <AD05> { [         y,          Y,    leftarrow,          yen ] };
+    key <AD06> { [         f,          F,      dstroke,  ordfeminine ] };
+    key <AD07> { [         g,          G,          eng,          ENG ] };
+    key <AD08> { [         c,          C,    copyright,    copyright ] };
+    key <AD09> { [         r,          R,   registered,   registered ] };
+    key <AD10> { [         l,          L,      lstroke,      Lstroke ] };
+    key <AD11> { [     comma,  semicolon                            ] };
+    key <AD12> { [    slash, asciitilde, dead_ogonek             ] };
+
+    ///////////////////////////////////////
+    // ASDF
+    ///////////////////////////////////////
+    key <AC01> { [         a,          A,    braceleft ] };
+    key <AC02> { [         o,          O,  bracketleft ] };
+    key <AC03> { [         e,          E, bracketright ] };
+    key <AC04> { [         u,          U,   braceright ] };
+    key <AC05> { [         i,          I ] };
+    key <AC06> { [         d,          D ] };
+    key <AC07> { [         h,          H ] };
+    key <AC08> { [         t,          T ] };
+    key <AC09> { [         n,          N ] };
+    key <AC10> { [         s,          S ] };
+    key <AC11> { [     minus, underscore, dead_belowdot, dead_abovedot ] };
+
+    ///////////////////////////////////////
+    // <> ZXCVB
+    ///////////////////////////////////////
+    key <AB01> { [    period,   colon, periodcentered, dead_abovedot ] };
+    key <AB02> { [         q,          Q] };
+    key <AB03> { [         j,          J ] };
+    key <AB04> { [         k,          K] };
+    key <AB05> { [         x,          X] };
+    key <AB06> { [         b,          B] };
+    key <AB07> { [         m,          M] };
+    key <AB08> { [         w,          W,      lstroke,      Lstroke ] };
+    key <AB09> { [         v,          V] };
+    key <AB10> { [         z,          Z] };
+};

Update the symbols file

$ cd /usr/share/X11/xkb/symbols
$ sudo xkbcomp -lhlpR '*' -o ../symbols.dir

Logout and login. Presto!

w2d2: Request new chunk

Read: http://worldmodscode.wordpress.com/2011/12/26/practical-garbage-collection-part-1-introduction/

Started on the main part of the buddy allocator.

reuest_chunk(info_item_t *root, int targetk);

Tests to cover this requesting zero levels down (targetk = k), one level down (targetk = k-1), two levels down (targetk = k-2) and all the way down (targetk = 0). Failing so far.

w1d5: Thought: Weak links

Weak links is a good addition/future work Each memory chunk would have a back pointer to the headers where handles are stored.

struct weak_handle_t;

struct chunk_info_t {

    // ...

    struct weak_handle_t *weak_handle; // linked list

    // ...

};

struct handle_t {
    chunk_info_t *chunk;

};
struct weak_handle_t {
    struct handle_t *handle; // not for inheritance use. NULL when auto-free'd
};

Handy for caches where data should be thrown out as needed.

w1d4: Buddy chunk/free list

Background
The buddy allocator allocates chunks of memory which is then split as needed. Each chunk is a even multiple of 2^k * MIN_CHUNK_SIZE. This leads to wasting memory, which is called internal fragmentation. Chunks are stored on a free list for each k, which itself is a list.

An item contains k, pointer to smaller item and the free list which is a pointer to a chunk.
A chunk contains a, b of size k and a pointer to the next chunk.

The root item is the largest chunk size available rounded up to the nearest power of 2. New chunks are fit into the proper k' by log2(n/MIN_CHUNK_SIZE). If there is no such k' yet, a new item is created with the smaller k' (iteratively, if k-k'>1) and new chunks created by splitting one of  the larger chunk's a or b members in half.


Work log
Item, chunk, constructors, destructors, splitting next. Unit tests for init functions written.

w1d3: Testing framework, mentor meeting, WWAN network

I got acquianted with Google Test. On Ubuntu Oneiric it doesn't show up in the apt listing and needs libpthread for linking. The first test verifies that balloc() returns non-NULL for a memory chunk smaller than the maximum amount of memory available, set by binit(size_t).  I implemented a trivial alloc/free for the test to pass.

There will be both black box testing, on the client side, and white box testing, on the allocator side. Client side is easily tested by feeding it random numbers and randomly freeing memory. For this, a graphical representation of the heap would be useful to spot used blocks and holes.
Internally, I expect verifying data structure invariants to be the most useful tests.

I had my weekly 30-min meeting with my mentor at Opera. The following topics were discussed:

• how a buddy allocator works (me presenting)
• compacting is the knapsack problem and hard to do right.
• using a priority list of blocks for speeding up incremental compacting
• overriding operator*() for automatic locking
• modifying memory access, which in itself is another thesis topic

Finally, I picked up a WWAN subscription so I can work from any location.

w1d2: Memory refresh: how does the Buddy allocator work?

Half day today.

I read up on the Buddy allocator and did a manual step-by-step allocation/free cycle on paper.
Fired up Vim, src/buddy/buddy.{h,c} stubs.

w1d1: Misc. administrative tasks

I renewed my Chalmers key card.
I looked around in the CS&E-facilities.
I sat in Linsen/the ED house and looked at people.
I talked to and sent Koen an e-mail about continuing to be my examiner.
I wrote the time plan (in Swedish) found on this site.