第2回 LILO CodeReading 勉強会参加記

第2回LILO CodeReading勉強会の2日目に行ってきました。ひらさんによるLinuxにおけるメモリアロケータの話が聴けました。今回が初参加ですが，なかなか面白かったです。今上記リンク先のプログラムを見返すと，実際の内容とちょっと違うような…。

とりあえず解説を聴講しながら各メモリアロケータアルゴリズムのシミュレーションをC++で（実質はCですが）粗く実装してみたので，勉強会参加の成果としてはっつけておきます。

資源マップアロケータ (first fit)
バディシステム
ゾーンアロケータ

資源マップアロケータ

first fit の資源マップアロケータ (resource-map-allocator.cpp) です。

#include <stdio.h>
#include <stdlib.h>

struct Node {
  int start;
  int size;
  Node *next;
};

Node *new_node(int start, int size) {
  Node *node = (Node*)malloc( sizeof(Node) );
  node->start = start;
  node->size = size;
  node->next = NULL;
}

void free_node(Node *node) {
  free(node);
}

void free_nodes(Node *node) {
  if (node == NULL) { return; }

  Node *next = node->next;
  free_node(node);

  free_nodes(next);
}

void print_nodes(Node *root) {
  if (root == NULL) { return; }

  for (Node *node = root; node; node = node->next) {
    printf("[%4d,%4d] ", node->start, node->size);
  }
  printf("\n");
}

Node *init_memory(int total) {
  Node *root = new_node(0, 0);
  root->next = new_node(0, 1024);
  root->next->next = new_node(1024, 0);
  return root;
}

bool myallocate(Node *root, int size) {
  if (root == NULL) { return false; }

  Node *prev = root;
  for (Node *node = root->next; node; prev = node, node = node->next) {
    if (node->size < size) { continue; }

    node->start += size;
    node->size -= size;

    if (node->size == 0) {
      prev->next = node->next;
      free_node(node);
    }

    return true;
  }

  return false;
}

bool myfree(Node *root, int start, int size) {
  if (root == NULL) { return false; }

  Node *prev = root;
  for (Node *node = root->next; node != NULL; prev = node, node = node->next) {
    if (start < node->start) {
      if (start < prev->start + prev->size) {
        return false;
      } else if (node->start < start + size) {
        return false;
      }

      prev->next = new_node(start, size);
      prev->next->next = node;

      return true;
    }
  }

  return false;
}

bool myallocate_verbose(Node *root, int size) {
  bool success = myallocate(root, size);

  if (success) {
    printf("Memory allocated: size=%d\n", size);
  } else {
    printf("Out of memory!\n");
  }

  return success;
}

bool myfree_verbose(Node *root, int start, int size) {
  bool success = myfree(root, start, size);

  if (success) {
    printf("Memory freed: [%4d,%4d]\n", start, size);
  } else {
    printf("Failed to free memory [%4d,%4d]\n", start, size);
  }

  return success;
}

int main() {
  Node *root = init_memory(1024);
  print_nodes(root);

  if ( !myallocate_verbose(root, 256) ) { return 0; }
  print_nodes(root);

  if ( !myallocate_verbose(root, 320) ) { return 0; }
  print_nodes(root);

  myfree_verbose(root, 0, 128);
  print_nodes(root);

  if ( !myallocate_verbose(root, 42) ) { return 0; }
  print_nodes(root);

  if ( !myallocate_verbose(root, 128) ) { return 0; }
  print_nodes(root);

  if ( !myallocate_verbose(root, 256) ) { return 0; }
  print_nodes(root);

  if ( !myallocate_verbose(root, 40) ) { return 0; }
  print_nodes(root);

  if ( !myallocate_verbose(root, 64) ) { return 0; }
  print_nodes(root);

  myfree_verbose(root, 1000, 128);
  print_nodes(root);

  myfree_verbose(root, 1000, 24);
  print_nodes(root);


  free_nodes(root);
  return 0;
}

動作（カッコの中は空き領域の [開始位置,サイズ] ）：

[   0,   0] [   0,1024] [1024,   0] 
Memory allocated: size=256
[   0,   0] [ 256, 768] [1024,   0] 
Memory allocated: size=320
[   0,   0] [ 576, 448] [1024,   0] 
Memory freed: [   0, 128]
[   0,   0] [   0, 128] [ 576, 448] [1024,   0] 
Memory allocated: size=42
[   0,   0] [  42,  86] [ 576, 448] [1024,   0] 
Memory allocated: size=128
[   0,   0] [  42,  86] [ 704, 320] [1024,   0] 
Memory allocated: size=256
[   0,   0] [  42,  86] [ 960,  64] [1024,   0] 
Memory allocated: size=40
[   0,   0] [  82,  46] [ 960,  64] [1024,   0] 
Memory allocated: size=64
[   0,   0] [  82,  46] [1024,   0] 
Failed to free memory [1000, 128]
[   0,   0] [  82,  46] [1024,   0] 
Memory freed: [1000,  24]
[   0,   0] [  82,  46] [1000,  24] [1024,   0]

Linked Listを辿っていって，空きが見つかればそこを確保，最後まで見ていって見つからなければ Out of memory という単純なアルゴリズムです。ひらさん曰く，「確保した領域と完全に一致しない領域でも解放ができるのが特徴の一つ」とのこと。

バディシステム

続いてバディシステム (buddy-allocator.cpp) です。

#include <stdio.h>
#include <stdlib.h>

struct Node {
  int start;
  int size;
  Node *next;
};

struct Header {
  int size;
  Node *items;
};

Node *new_node(int start, int size) {
  Node *node = (Node*)malloc( sizeof(Node) );
  node->start = start;
  node->size = size;
  node->next = NULL;
  return node;
}

void free_node(Node *node) {
  if (node == NULL) { return; }
  free(node);
}

Node *init_memory(Header *lh, int total, int minimum) {
  int i = 0;
  for (int size = minimum; size <= total; size *= 2) {
    lh[i].size = size;
    lh[i].items = NULL;
    i++;
  }
  lh[i].size = 0;
  lh[i].items = NULL;

  if (i > 0) {
    lh[i-1].items = new_node(0, lh[i-1].size);
  }
}

Node *myallocate(Header *lh, int size) {
  int alloc = -1;
  for (int i = 0; lh[i].size > 0; i++) {
    if (lh[i].size >= size && lh[i].items != NULL) { alloc = i; break; }
  }
  if (alloc < 0) { return NULL; }

  int alloc_size = lh[alloc].size;
  Node *node = lh[alloc].items;

  if (alloc_size / 2 < size) {
    lh[alloc].items = node->next;

    return node;
  } else {
    lh[alloc].items = node->next;

    int half_size = node->size / 2;
    Node *node2 = new_node(node->start + half_size, half_size);
    node->next = node2;
    node->size = half_size;

    for (int i = 0; lh[i].size > 0; i++) {
      if (lh[i].size == half_size) {
        Node *tmp_node = lh[i].items;
        lh[i].items = node;
        node2->next = tmp_node;
        break;
      }
    }

    return myallocate(lh, size);
  }
}

// idx : index in lh
void merge(Header *lh, int idx) {
  Node *target = lh[idx].items; // target node to be merged
  if (target == NULL) { return; }

  int boundary = target->size * 2;
  bool on_boundary = (target->start % boundary == 0);
  int buddy_start = on_boundary ? target->start + target->size : target->start - target->size;
//printf("boundary=%d, on_boundary=%d, buddy_start=%d\n", boundary, on_boundary, buddy_start);

  Node *prev = target;
  for (Node *node = target->next; node != NULL; prev = node, node = node->next) {
    if (node->start == buddy_start) {
      prev->next = node->next;
      free_node(node);

      lh[idx].items = target->next;

      if (!on_boundary) { target->start = buddy_start; }
      target->size *= 2;

      target->next = lh[idx+1].items;
      lh[idx+1].items = target;

      merge(lh, idx+1);
      return;
    }
  }
}

bool myfree(Header *lh, Node *node) {
  int start = node->start;
  int size = node->size;

  for (int i = 0; lh[i].size > 0; i++) {
    if (lh[i].size == size) {
      node->next = lh[i].items;
      lh[i].items = node;
      merge(lh, i);
      return true;
    }
  }

  return false;
}

void print_header(Header *lh) {
  for (int i = 0; lh[i].size > 0; i++) {
    int items = 0;
    for (Node *node = lh[i].items; node != NULL; node = node->next) {
      items++;
    }
    printf("[%d:items=%d] ", lh[i].size, items);
  }
  printf("\n");
}

Node *myallocate_verbose(Header *lh, int size) {
  Node *node = myallocate(lh, size);

  if (node != NULL) {
    printf("Memory allocated: start=%d, size=%d\n", node->start, node->size);
  } else {
    printf("Out of memory!\n");
  }

  return node;
}

bool myfree_verbose(Header *lh, Node *node) {
  int start = node->start;
  int size = node->size;

  bool success = myfree(lh, node);

  if (success) {
    printf("Memory freed: start=%d, size=%d\n", start, size);
  } else {
    printf("Free failed!\n");
  }

  return success;
}

int main() {
  Header lh[128]; // list header

//  Node *root = new_node(0, 1024);
  init_memory(lh, 256, 1);
  print_header(lh);

  Node *n1 = myallocate_verbose(lh, 64);
  if (!n1) { return 1; }
  print_header(lh);

  Node *n2 = myallocate_verbose(lh, 8);
  if (!n2) { return 1; }
  print_header(lh);

  Node *n3 = myallocate_verbose(lh, 64);
  if (!n3) { return 1; }
  print_header(lh);

  myfree_verbose(lh, n1); n1 = NULL;
  print_header(lh);

  myfree_verbose(lh, n2); n2 = NULL;
  print_header(lh);

  myfree_verbose(lh, n3); n3 = NULL;
  print_header(lh);

  // free_all(lh); // not implemented

  return 0;
}

動作（カッコの中はリストヘッダの [サイズ:アイテム数]）：

[1:items=0] [2:items=0] [4:items=0] [8:items=0] [16:items=0] [32:items=0] [64:items=0] [128:items=0] [256:items=1] 
Memory allocated: start=0, size=64
[1:items=0] [2:items=0] [4:items=0] [8:items=0] [16:items=0] [32:items=0] [64:items=1] [128:items=1] [256:items=0] 
Memory allocated: start=64, size=8
[1:items=0] [2:items=0] [4:items=0] [8:items=1] [16:items=1] [32:items=1] [64:items=0] [128:items=1] [256:items=0] 
Memory allocated: start=128, size=64
[1:items=0] [2:items=0] [4:items=0] [8:items=1] [16:items=1] [32:items=1] [64:items=1] [128:items=0] [256:items=0] 
Memory freed: start=0, size=64
[1:items=0] [2:items=0] [4:items=0] [8:items=1] [16:items=1] [32:items=1] [64:items=2] [128:items=0] [256:items=0] 
Memory freed: start=64, size=8
[1:items=0] [2:items=0] [4:items=0] [8:items=0] [16:items=0] [32:items=0] [64:items=1] [128:items=1] [256:items=0] 
Memory freed: start=128, size=64
[1:items=0] [2:items=0] [4:items=0] [8:items=0] [16:items=0] [32:items=0] [64:items=0] [128:items=0] [256:items=1]

これは実質的に2分木で，1つのノードを2つの兄弟ノードに分割，あるいは逆に合体するのですが，その兄弟を相棒 (buddy) とみなすのでバディシステムなのだそうです。分割/合体は再帰呼び出しになっているので，その中で printf をかますと動作が分かりやすくなるかも。

上の実装のうち合体 (merge) 部分はかなりナイーブな実装にしていて，Linked Listを走査してバディノードを探すというわけのわからないことをやっています。でも，実際は各メモリ位置にページ構造体のようなものがあるらしくて，メモリ位置決め打ちでそこにアクセスすることで，リストの線形走査が不必要になります。

Linux Kernel 2.4 ではさらなる高速化のために，ページ構造体へのアクセスではなく，使用中/未使用を表すビットマップ (bit vector) を使っていたそうなのですが，コンピュータ稼動中のメモリの抜き差しをサポートしようとした場合に bit vector の初期化が複雑になりすぎるので 2.6 では止めたとのことです。へー。Linux Kernelなんて部分でも maintainability > 速度なことが普通にあるのか。

ゾーンアロケータ

最後にゾーンアロケータ (zone-allocator.cpp) です。でも，ユーザプログラムからの呼び出しインタフェースがよく分からなくて，たぶん勘違いした変な設計になっています。さらにメモリ解放部分は未実装です。まあ，雰囲気だけでも。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// GCed?

struct Element {
  void *item;
  bool used;
  Element *next;
};

struct Zone {
  char *name;
  Zone *prev, *next;
  Element *free_elements;
};

struct ZoneAllocator {
  Zone *first;
  Zone *last;
};

Element *new_element(void *obj, int obj_size) {
  Element *e = (Element*)malloc( sizeof(Element) );

  void *copy = malloc(obj_size);
  memcpy(copy, obj, obj_size);

  e->item = copy;
  e->used = false;
  e->next = NULL;
  return e;
}

Zone *new_zone(char *name) {
  Zone *zone = (Zone*)malloc( sizeof(Zone) );
  zone->name = name;
  zone->prev = NULL;
  zone->next = NULL;
  zone->free_elements = NULL;
  return zone;
}

void add_new_zone(ZoneAllocator *za, char *name, void *obj, int n) {
  Zone *zone = new_zone(name);

  Zone *last = za->last;

  last->prev->next = zone;
  zone->prev = last->prev;

  last->prev = zone;
  zone->next = last;

  if (n > 0) {
    Element *first = new_element(obj, sizeof(obj));

    zone->free_elements = first;
    Element *prev = first;
    for (int i = 1; i < n; i++) {
       prev->next = new_element(obj, sizeof(obj));
       prev = prev->next;
    }
  }
}

void print_zones(ZoneAllocator *za) {
  for (Zone *zone = za->first; zone != NULL; zone = zone->next) {
    int elements = 0, free = 0;
    for (Element *e = zone->free_elements; e != NULL; e = e->next) {
      elements++;
      if (!e->used) { free++; }
    }
    printf("[%s:elements=%d,free=%d] ", zone->name, elements, free);
  }
  printf("\n");
}

struct ObjA {
  int n;
};

ZoneAllocator *init_zone_allocator() {
  ZoneAllocator *za = (ZoneAllocator*)malloc( sizeof(ZoneAllocator) );
  za->first = new_zone("FIRST");
  za->last  = new_zone("LAST");

  za->first->next = za->last;
  za->last->prev = za->first;

  return za;
}

void *myallocate(ZoneAllocator *za, const char *name) {
  Zone *found = NULL;
  for (Zone *zone = za->first; zone != NULL; zone = zone->next) {
    if ( strcmp(zone->name, name) == 0 ) {
      found = zone;
      break;
    }
  }
  if (found == NULL) { return NULL; }

  for (Element *e = found->free_elements; e != NULL; e = e->next) {
    if (e->used) { continue; }

    e->used = true;

    return e->item;
  }

  return NULL;
}

int main() {
  ZoneAllocator *za = init_zone_allocator();
  print_zones(za);

  ObjA obja = {0};

  add_new_zone(za, "ObjA", &obja, 128);
  print_zones(za);

  ObjA *obj = (ObjA*)myallocate(za, "ObjA");
  if (obj == NULL) { printf("obj not allocated!\n"); }
  print_zones(za);

  return 0;
}

動作です：

[FIRST:elements=0,free=0] [LAST:elements=0,free=0] 
[FIRST:elements=0,free=0] [ObjA:elements=128,free=128] [LAST:elements=0,free=0] 
[FIRST:elements=0,free=0] [ObjA:elements=128,free=127] [LAST:elements=0,free=0]

一応 free なオブジェクトを1つ要求はできていますが... まあ，中途半端ですね。

スラブアロケータ

その他スラブアロケータ (slab allocator) の話もあったのですが，これは時間が足りなくて全く実装できませんでした。アルゴリズムの解説を聞きながら同時に実装するのはやっぱりちょっと難しいです。時間的に。

こういうアルゴリズムはあまり詳しい話を聞く機会も，たとえシミュレーションでも実装できる機会もそれほど多くないので，非常にためになりました。ありがとうございました。