Generic Associative Array Implementation

Generic associative array의 성질

`Generic Associative Array Implementation`은 opaque object pointer를 보관하는 container입니다. 구현은 pointer가 실제로 어디를 가리키는지 또는 무엇을 가리키는지 알 필요가 없습니다.

• object 자체에 array linkage block을 넣지 않습니다. metadata block이 object를 가리키므로 같은 object를 여러 array에 동시에 둘 수 있습니다.
• object를 찾으려면 index key가 필요하며 key는 고유해야 합니다. 같은 key로 insert하면 기존 object를 교체합니다.
• index key는 길이가 서로 달라도 되고 임의 길이일 수 있지만, 길이에 따른 차이가 나타나기 전에 key 앞부분에 length를 encode하는 편이 좋습니다.
• key에 hash를 넣어 object를 array 전체에 흩을 수 있습니다.
• array를 iteration할 수 있지만 object가 반드시 key 순서로 나오지는 않습니다.
• iterator가 RCU read lock을 잡으면 수정 중에도 iteration할 수 있습니다. object를 두 번 볼 수 있으므로 문제가 되면 modifier와 lock해야 하지만 삭제되지 않은 object를 놓치지는 않습니다.
• index key로 lookup할 수 있으며 lookup thread가 RCU read lock을 잡으면 수정과 동시에 검색할 수 있습니다.

내부 구현은 radix tree처럼 각 level에서 index key nibble로 선택하는 16-pointer node tree를 사용합니다. memory 효율을 높이기 위해 single-occupancy node 연속 구간을 shortcut으로 건너뛰고, node가 가득 차 새 branch가 필요해질 때까지 남는 slot에 leaf object pointer를 함께 pack합니다.

Public API와 edit script

public API는 `<linux/assoc_array.h>`에 있고 associative array의 root는 다음 structure입니다.

struct assoc_array {
        ...
};

다음 명령으로 `CONFIG_ASSOCIATIVE_ARRAY`를 활성화해 code를 선택합니다.

./script/config -e ASSOCIATIVE_ARRAY

insert와 delete function은 나중에 적용할 `edit script`를 생성합니다. internal tree에 설치할 metadata block을 미리 allocate하고 적용 시 제거할 block도 기록하므로 실제 변경 시 `ENOMEM` 위험이 없습니다.

script 적용 뒤에는 dead block과 dead object도 기록하여 나중에 해제합니다. RCU grace period가 지난 뒤 free하므로 access function은 RCU read lock 아래 계속 진행할 수 있습니다.

API에서 script는 다음 opaque pointer type으로 보입니다.

struct assoc_array_edit;

edit script를 적용하는 function은 다음과 같습니다.

void assoc_array_apply_edit(struct assoc_array_edit *edit);

`assoc_array_apply_edit()`은 여러 write barrier를 배치하며 edit을 실행해 RCU read lock 아래의 access가 계속되게 합니다. 이어 script를 `call_rcu()`에 넘겨 script와 가리키는 dead object를 해제합니다.

edit script를 취소하는 function은 다음과 같습니다.

void assoc_array_cancel_edit(struct assoc_array_edit *edit);

`assoc_array_cancel_edit()`은 script와 preallocated memory를 즉시 해제합니다. insert용 script였다면 새 object는 해제하지 않으므로 caller가 직접 release해야 합니다. 두 function은 실패하지 않습니다.

assoc_array_ops callback 규약

여러 API function은 다음 operation table을 받습니다.

struct assoc_array_ops {
        ...
};

모든 method를 제공해야 합니다.

unsigned long (*get_key_chunk)(const void *index_key, int level);

`get_key_chunk()`는 caller가 제공한 index key에서 `level` bit 위치부터 `ASSOC_ARRAY_KEY_CHUNK_SIZE` bits를 반환합니다. `level`은 chunk size의 배수이며 오류는 발생하지 않습니다.

unsigned long (*get_object_key_chunk)(const void *object, int level);

`get_object_key_chunk()`는 같은 방식으로 array 안 object의 index key에서 chunk를 얻습니다.

bool (*compare_object)(const void *object, const void *index_key);

`compare_object()`는 object와 index key를 비교해 일치하면 `true`, 아니면 `false`를 반환합니다.

int (*diff_objects)(const void *object, const void *index_key);

`diff_objects()`는 지정 object의 index key가 주어진 key와 처음 달라지는 bit position을 반환하고 같으면 `-1`을 반환합니다.

void (*free_object)(void *object);

`free_object()`는 object를 해제합니다. `assoc_array_apply_edit()` 뒤 RCU grace period가 지난 후 호출될 수 있으므로 module unload에는 `synchronize_rcu()`가 필요할 수 있습니다.

초기화, insert·replace와 delete

associative array base structure는 다음 function으로 초기화하며 실패하지 않습니다.

void assoc_array_init(struct assoc_array *array);

object insert 또는 replace interface는 다음과 같습니다.

struct assoc_array_edit *
assoc_array_insert(struct assoc_array *array,
                   const struct assoc_array_ops *ops,
                   const void *index_key,
                   void *object);

`assoc_array_insert()`에 넘기는 object pointer의 least significant bit는 내부 type mark에 쓰이므로 0이어야 합니다. 같은 key의 object가 이미 있으면 새 object로 교체하고 기존 object는 자동 해제합니다.

`index_key`는 operation table method에 전달할 key 정보를 담습니다. function은 array를 직접 바꾸지 않고 적용해야 할 edit script를 반환하며 out-of-memory면 `-ENOMEM`을 반환합니다. caller는 다른 modifier와 배타적으로 lock해야 합니다.

object delete interface는 다음과 같습니다.

struct assoc_array_edit *
assoc_array_delete(struct assoc_array *array,
                   const struct assoc_array_ops *ops,
                   const void *index_key);

`assoc_array_delete()`는 지정 key와 일치하는 object를 삭제할 edit script를 만듭니다. `index_key`는 ops method로 전달됩니다. out-of-memory면 `-ENOMEM`, object를 찾지 못하면 `NULL`을 반환하며 caller는 다른 modifier와 배타적으로 lock해야 합니다.

clear, destroy와 garbage collection

모든 object를 지우고 array를 완전히 비우는 interface입니다.

struct assoc_array_edit *
assoc_array_clear(struct assoc_array *array,
                  const struct assoc_array_ops *ops);

`assoc_array_clear()`도 직접 수정하지 않고 적용할 edit script를 반환하며 `-ENOMEM`이 가능하고 다른 modifier와 배타적으로 lock해야 합니다.

array 내용을 destroy하고 완전히 비우는 interface입니다.

void assoc_array_destroy(struct assoc_array *array,
                         const struct assoc_array_ops *ops);

`assoc_array_destroy()`는 memory release를 RCU로 지연하지 않습니다. 지연하려면 추가 allocation이 필요하기 때문입니다. 따라서 실행 중 다른 thread가 RCU read lock 아래 array를 traverse하면 안 되며 caller는 modifier와 accessor 모두에 대해 배타적으로 lock해야 합니다.

garbage collection interface는 다음과 같습니다.

int assoc_array_gc(struct assoc_array *array,
                   const struct assoc_array_ops *ops,
                   bool (*iterator)(void *object, void *iterator_data),
                   void *iterator_data);

`assoc_array_gc()`는 모든 object를 `iterator()`에 전달합니다. callback이 `true`면 object를 유지하고 `false`면 해제합니다. 유지할 때는 반환 전에 필요한 refcount 증가를 수행해야 합니다.

iteration 중 가능한 경우 internal tree를 pack하여 node 수를 줄입니다. `iterator_data`는 callback에 그대로 전달할 뿐 API가 해석하지 않습니다. 성공은 0, memory 부족은 `-ENOMEM`입니다.

GC가 진행되는 동안 다른 thread가 RCU read lock 아래 iteration 또는 search할 수 있습니다. caller는 다른 modifier에 대해서만 배타적으로 lock해야 합니다.

iteration과 key lookup

모든 object를 순회하는 interface는 다음과 같습니다.

int assoc_array_iterate(const struct assoc_array *array,
                        int (*iterator)(const void *object,
                                        void *iterator_data),
                        void *iterator_data);

`assoc_array_iterate()`는 각 object를 callback에 전달하고 `iterator_data`를 callback 전용 data로 넘깁니다. RCU read lock을 잡으면 수정과 동시에 사용할 수 있지만 일부 object를 두 번 볼 수 있습니다. 중복이 문제라면 modification을 lock해야 하며 algorithm은 object를 놓치지 않습니다.

array가 비어 있으면 0을, 그렇지 않으면 마지막 callback 결과를 반환합니다. callback이 0이 아닌 값을 반환하면 iteration을 즉시 멈춥니다.

index key로 object를 찾는 interface입니다.

void *assoc_array_find(const struct assoc_array *array,
                       const struct assoc_array_ops *ops,
                       const void *index_key);

`assoc_array_find()`는 internal tree를 직접 따라 key가 지정한 object로 갑니다. RCU read lock을 잡으면 수정과 동시에 사용할 수 있습니다. 찾으면 object를 반환하고 `*_type`을 object type으로 설정하며, 찾지 못하면 `NULL`을 반환합니다.

Index key 형식과 scattering

index key는 어떤 형식도 가능하지만 algorithm은 key 길이를 따로 알지 못합니다. 길이 차이가 comparison에 영향을 주기 전에 key 앞부분에 length를 포함할 것을 강하게 권장합니다.

그러면 길이가 다른 key의 leaf는 서로 흩어지고 같은 길이 key는 함께 모입니다. key 나머지 부분의 hash를 시작에 두면 keyspace 전체 scattering을 최대화할 수 있습니다.

scattering이 좋을수록 internal tree는 더 넓고 낮아집니다. 나쁘더라도 shortcut이 있고 node가 leaf와 metadata pointer를 섞어 담을 수 있어 심각한 문제는 아닙니다.

index key는 machine word chunk로 읽고 각 chunk를 level당 nibble, 즉 4 bits로 나눕니다. 32-bit CPU에서는 word 하나로 8 levels, 64-bit CPU에서는 16 levels를 처리합니다. scattering이 매우 나쁘지 않다면 특정 key에서 word 하나보다 많이 사용할 가능성은 작습니다.

내부 node와 shortcut

associative array 내부 tree는 node와 shortcut 두 종류 metadata block으로 구성됩니다.

node는 slot array이며 각 slot에는 네 종류 가운데 하나가 들어갑니다.

• `NULL` pointer: 빈 slot
• object pointer: leaf
• 다음 level node pointer
• shortcut pointer

기본 내부 tree layout과 leaf packing

shortcut을 제외하면 node는 multilevel tree를 이룹니다. index keyspace는 node에 의해 엄격히 분할되고 node는 고정 level에 놓입니다. 원문의 7-node ASCII tree를 연결 관계로 구조화하면 다음과 같습니다.

다른 metadata node가 없다고 가정하면 key prefix별 담당 node는 다음과 같습니다.

예제 index key가 위치할 node는 다음과 같습니다.

memory 절약을 위해 node가 자기 keyspace의 모든 leaf를 담을 수 있으면 일부 leaf가 같은 logical slot을 원하더라도 metadata pointer 없이 모두 그 node에 둡니다.

node는 leaf와 metadata pointer를 섞어 담을 수 있습니다. metadata pointer는 keyspace subdivision과 일치하는 slot에 있어야 하지만 leaf는 metadata가 차지하지 않은 아무 slot에나 둘 수 있습니다. metadata slot의 prefix와 일치하는 leaf는 반드시 그 pointer가 가리키는 subtree에 있으므로 같은 node에 남지 않습니다.

single-occupancy level을 건너뛰는 shortcut

shortcut은 keyspace 일부를 한 번에 건너뛰는 metadata record로, 여러 level에 이어진 single-occupancy node를 대체하여 memory를 절약하고 traversal을 빠르게 합니다.

tree root 자체가 shortcut일 수도 있습니다. 예를 들어 key prefix `1111`을 공유하는 node가 17개 이상이면 insertion algorithm은 `1111` keyspace를 한 번에 건너뛰어 실제 차이가 생기는 fourth level로 가는 shortcut을 넣습니다.

node split·collapse와 non-recursive iteration

node maximum capacity는 leaf와 metadata pointer 합계 16개입니다. 17번째 object를 넣으려 하면 현재 level에서 공통 key segment를 가진 leaf 최소 두 개를 그 segment slot에 root를 둔 별도 node로 분리합니다.

full node의 leaf와 새 leaf가 충분히 비슷하면 tree에 shortcut도 삽입합니다. 한 node 아래 subtree의 object 수가 16개 이하로 줄면 subtree를 node 하나로 collapse하고 가능하면 root 방향으로 연쇄 적용합니다.

각 node와 shortcut은 parent back pointer와 parent에서 자신을 가리키는 slot number를 가집니다. non-recursive iteration은 이를 이용해 parent 방향으로 올라가고 parent node의 slot `N + 1`부터 계속하여 stack 없이도 전진합니다.

이 back pointer 구조는 modification과 iteration을 동시에 수행할 때 추가 주의가 필요합니다.

수정과 iteration의 동시 수행

동시 수정과 iteration에서는 다음 경우를 고려합니다.

• 단순 insert/replace: barrier 뒤 `NULL` 또는 기존 matching leaf pointer만 새 leaf로 교체합니다. metadata는 바뀌지 않고 기존 leaf는 RCU grace period 뒤 해제합니다.
• 단순 delete: 기존 matching leaf를 지웁니다. metadata는 바뀌지 않고 leaf는 grace period 뒤 해제합니다.
• 아직 들어가지 않은 subtree 일부를 insertion이 교체: 아직 그 pointer에 도달하지 않았고 ancestor layout은 바뀌지 않으므로 iteration에 영향이 없습니다.
• 현재 처리 중인 node를 insertion이 교체: anchoring pointer를 이미 지났으므로 back pointer를 따라갈 때까지 새 layout으로 전환하지 않습니다. 다만 뒤쪽 slot의 새 branch로 split된 leaf를 다시 볼 수 있습니다.
• 현재 처리하는 dependent branch의 ancestor node를 insertion이 교체: back pointer를 따라가기 전까지 영향이 없으며 앞 경우와 비슷합니다.
• 현재 아래에 있는 branch를 deletion이 collapse: back pointer가 새 node를 보기 전에 그 parent로 돌려보냅니다. 폐기된 subtree는 같은 slot에 그대로 root되어 있으므로 slot + 1로 돌아가 두 번 처리하지 않습니다.

obsolete block과 leaf는 RCU grace period 뒤 해제됩니다. walk나 iteration을 수행하는 모든 code가 RCU read lock을 잡는 한 이전 superstructure가 사용 중 사라지지 않습니다.