softflowdのデータ構造

softflowdは、筆者がメンテナンスしているソフトウェアですが、元々はDamien Millerという方がオリジナルの作者です。そのため、自分があまりきちんと把握せずにメンテしている部分もあります(正確に言うと自分で書いていないから忘れてしまう)。そのあまりきちんと把握していない部分にsoftflowd内部で使われているFlowのメモリ管理がわからなくなったのでコードを読み直して調べなおしました。そのメモです。

分析したのはsoftflowd.hのFLOWTRACK構造体です。

struct FLOWTRACK {
  /* The flows and their expiry events */
  FLOW_HEAD (FLOWS, FLOW) flows;        /* Top of flow tree */
  EXPIRY_HEAD (EXPIRIES, EXPIRY) expiries;      /* Top of expiries tree */

  struct freelist flow_freelist;        /* Freelist for flows */
  struct freelist expiry_freelist;      /* Freelist for expiry events */

  struct FLOWTRACKPARAMETERS param;
};

freelist

リストを実現する構造体です。一定のエントリ数分まとまってメモリ領域を確保するようになっており単純なリストに比べて連続した領域をとるようになっています。freelist.hで定義されているstruct freelistは以下の内容です。

struct freelist {
        size_t allocsz;
        size_t nalloc;
        size_t navail;
        void **free_entries;
};

allocszはallocate sizeの略と想定され、free_entriesが指し示す先の各エントリのサイズを意味しています。
- softflowd.cのinit_flowtrackにおいてfreelist_init (&ft->flow_freelist, sizeof (struct FLOW));を呼び出していますが、allocsz = sizeof (struct FLOW)の関係になります。
nallocは使用された数を示しています。
navailは使用されていない数つまり利用可能数を示しています。
free_entriesは二重ポインタですが、外側のポインタは可変長配列として使うためのポインタで、内側のポインタは実際の各エントリのポインタになっています。つまりポインタの配列の用途のために使っています。

freelist.hで定義されfreelist.cで実装されている関数は以下です。

void freelist_init(struct freelist *freelist, size_t allocsz);
- 初期化関数です。
- 第2引数のallocszを第1引数のfreelistの構造体のメンバのallocszに代入します。
- 第1引数のfreelistの構造体のメンバのNULL初期化されます。
void *freelist_get(struct freelist *freelist);
- キューから、エントリのポインタを一つ取り出します。
- navailが0、即ち(初期時を含めた)キューに空きエントリがない場合には、内部的にはfreelist_growというstatic関数を呼び出しキューを拡大します。
  - freelist_growでは、need = fl->nalloc * sizeof(*fl->free_entries);,realloc(fl->free_entries, need))により、エントリ数の不足した際にfree_entriesの配列サイズ(外側のポインタ)を2倍(*)のサイズにします。(*その前段の処理でnnedは元の値の2倍にするようになっています)
  - freelist_growでは、その後、need = (fl->nalloc - oldnalloc) * fl->allocsz;, malloc(need)により、追加したエントリ数分だけ、実際のエントリを確保できるようにメモリを確保します。
void freelist_put(struct freelist *freelist, void *p);
- fl->free_entries[fl->navail] = p;により、freelistのキューに、pを追加(返却)します。freelist構造体のnavailはインクリメントされます。

呼び出し元

softflowd.cにて以下の呼び出しを行っています。つまりFLOW構造体のポインタのリストと、EXPIRY構造体のポインタのリストを作成しています。

  freelist_init (&ft->flow_freelist, sizeof (struct FLOW));
  freelist_init (&ft->expiry_freelist, sizeof (struct EXPIRY));

ツリー

softflowd.hのFLOWTRACK構造体のFLOW_HEAD (FLOWS, FLOW) flows;は、treetype.hにおいて、configure時にオプションを与えない限りデフォルトでは:#define FLOW_HEAD RB_HEADという定義で赤黒木のアルゴリズムで管理されます。それの実態はsys-tree.hにあります。なお、treetype.hはHEADのみならずすべてのFLOW*をRB*にdefineしています。このヘッダファイルはBSD系に存在するファイルのコピーです。なのでFreeBSDのman-pageを読んだ方が良いかもしれません。

RB_HEADは以下の定義となっているため、

#define RB_HEAD(name, type)                                             \
struct name {                                                           \
        struct type *rbh_root; /* root of the tree */                   \
}

実際は、FLOW_HEAD (FLOWS, FLOW) flows;は、

struct FLOWS {
    struct FLOW *rbh_root
} flows;

と展開されます。

そして、sturct FLOWの中にはFLOW_ENTRY (FLOW) trp;が存在します。

struct FLOW {
    :
    FLOW_ENTRY (FLOW) trp;
    :
}

RB_ENTRYは以下の定義となっているため、

#define RB_ENTRY(type)                                                  \
struct {                                                                \
        struct type *rbe_left;          /* left element */              \
        struct type *rbe_right;         /* right element */             \
        struct type *rbe_parent;        /* parent element */            \
        int rbe_color;                  /* node color */                \
}

実際は、FLOW_ENTRY (FLOW) trp;は、

struct {
        struct FLOW *rbe_left;          /* left element */
        struct FLOW *rbe_right;         /* right element */
        struct FLOW *rbe_parent;        /* parent element */
        int rbe_color;                  /* node color */
} trp;

と展開されます。ツリー構造のため親と左右の子のポインタを持っています。

実際の使われ方

softflowd.cではフローをFLOW_FIND (FLOWS, &ft->flows, &tmp)で検索した後に、同一フローがなければ、flow = flow_get (ft)によりエントリを格納するメモリ領域のポインタを取得して、FLOW_INSERT (FLOWS, &ft->flows, flow);を行います。

softflowdのデータ構造#

freelist#

呼び出し元#

ツリー#

実際の使われ方#

softflowdのデータ構造

freelist

呼び出し元

ツリー

実際の使われ方