BPF_MAP_TYPE_BLOOM_FILTER | Linux 6.18.37

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

요약과 해설

map_bloom_filter.rst:1-174

Bloom filter map은 key 없이 value만 저장하며 false positive는 허용하지만 false negative는 허용하지 않는 probabilistic membership test를 제공합니다. 생성할 때 key size는 0이어야 합니다.

`max_entries`는 bitmap size 추정치이고 hard limit이 아닙니다. `map_extra`의 lower 4 bit로 hash 수를 정하며 hash를 늘리면 accuracy와 lookup cost가 함께 증가합니다.

Kernel은 push·peek helper를, userspace는 update·lookup API를 사용합니다. Peek 성공은 확정적인 존재가 아니므로 필요한 경우 secondary map lookup으로 false positive를 검증해야 합니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기

1 .. SPDX-License-Identifier: GPL-2.0-only

4 =========================

5 BPF_MAP_TYPE_BLOOM_FILTER

6 =========================

8 .. note::

9 - ``BPF_MAP_TYPE_BLOOM_FILTER`` was introduced in kernel version 5.16

11 ``BPF_MAP_TYPE_BLOOM_FILTER`` provides a BPF bloom filter map. Bloom

12 filters are a space-efficient probabilistic data structure used to

13 quickly test whether an element exists in a set. In a bloom filter,

14 false positives are possible whereas false negatives are not.

16 The bloom filter map does not have keys, only values. When the bloom

17 filter map is created, it must be created with a ``key_size`` of 0. The

18 bloom filter map supports two operations:

20 - push: adding an element to the map

21 - peek: determining whether an element is present in the map

23 BPF programs must use ``bpf_map_push_elem`` to add an element to the

24 bloom filter map and ``bpf_map_peek_elem`` to query the map. These

25 operations are exposed to userspace applications using the existing

26 ``bpf`` syscall in the following way:

28 - ``BPF_MAP_UPDATE_ELEM`` -> push

29 - ``BPF_MAP_LOOKUP_ELEM`` -> peek

31 The ``max_entries`` size that is specified at map creation time is used

32 to approximate a reasonable bitmap size for the bloom filter, and is not

33 otherwise strictly enforced. If the user wishes to insert more entries

34 into the bloom filter than ``max_entries``, this may lead to a higher

35 false positive rate.

37 The number of hashes to use for the bloom filter is configurable using

38 the lower 4 bits of ``map_extra`` in ``union bpf_attr`` at map creation

39 time. If no number is specified, the default used will be 5 hash

40 functions. In general, using more hashes decreases both the false

41 positive rate and the speed of a lookup.

43 It is not possible to delete elements from a bloom filter map. A bloom

44 filter map may be used as an inner map. The user is responsible for

45 synchronising concurrent updates and lookups to ensure no false negative

46 lookups occur.

48 Usage

49 =====

51 Kernel BPF

52 ----------

54 bpf_map_push_elem()

55 ~~~~~~~~~~~~~~~~~~~

57 .. code-block:: c

59 long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)

61 A ``value`` can be added to a bloom filter using the

62 ``bpf_map_push_elem()`` helper. The ``flags`` parameter must be set to

63 ``BPF_ANY`` when adding an entry to the bloom filter. This helper

64 returns ``0`` on success, or negative error in case of failure.

66 bpf_map_peek_elem()

67 ~~~~~~~~~~~~~~~~~~~

69 .. code-block:: c

71 long bpf_map_peek_elem(struct bpf_map *map, void *value)

73 The ``bpf_map_peek_elem()`` helper is used to determine whether

74 ``value`` is present in the bloom filter map. This helper returns ``0``

75 if ``value`` is probably present in the map, or ``-ENOENT`` if ``value``

76 is definitely not present in the map.

78 Userspace

79 ---------

81 bpf_map_update_elem()

82 ~~~~~~~~~~~~~~~~~~~~~

84 .. code-block:: c

86 int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)

88 A userspace program can add a ``value`` to a bloom filter using libbpf's

89 ``bpf_map_update_elem`` function. The ``key`` parameter must be set to

90 ``NULL`` and ``flags`` must be set to ``BPF_ANY``. Returns ``0`` on

91 success, or negative error in case of failure.

93 bpf_map_lookup_elem()

94 ~~~~~~~~~~~~~~~~~~~~~

96 .. code-block:: c

98 int bpf_map_lookup_elem (int fd, const void *key, void *value)

100 A userspace program can determine the presence of ``value`` in a bloom

101 filter using libbpf's ``bpf_map_lookup_elem`` function. The ``key``

102 parameter must be set to ``NULL``. Returns ``0`` if ``value`` is

103 probably present in the map, or ``-ENOENT`` if ``value`` is definitely

104 not present in the map.

105

106 Examples

107 ========

108

109 Kernel BPF

110 ----------

111

112 This snippet shows how to declare a bloom filter in a BPF program:

113

114 .. code-block:: c

115

116 struct {

117 __uint(type, BPF_MAP_TYPE_BLOOM_FILTER);

118 __type(value, __u32);

119 __uint(max_entries, 1000);

120 __uint(map_extra, 3);

121 } bloom_filter SEC(".maps");

122

123 This snippet shows how to determine presence of a value in a bloom

124 filter in a BPF program:

125

126 .. code-block:: c

127

128 void *lookup(__u32 key)

129 {

130 if (bpf_map_peek_elem(&bloom_filter, &key) == 0) {

131 /* Verify not a false positive and fetch an associated

132 * value using a secondary lookup, e.g. in a hash table

133 */

134 return bpf_map_lookup_elem(&hash_table, &key);

135 }

136 return 0;

137 }

138

139 Userspace

140 ---------

141

142 This snippet shows how to use libbpf to create a bloom filter map from

143 userspace:

144

145 .. code-block:: c

146

147 int create_bloom()

148 {

149 LIBBPF_OPTS(bpf_map_create_opts, opts,

150 .map_extra = 3); /* number of hashes */

151

152 return bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER,

153 "ipv6_bloom", /* name */

154 0, /* key size, must be zero */

155 sizeof(ipv6_addr), /* value size */

156 10000, /* max entries */

157 &opts); /* create options */

158 }

159

160 This snippet shows how to add an element to a bloom filter from

161 userspace:

162

163 .. code-block:: c

164

165 int add_element(struct bpf_map *bloom_map, __u32 value)

166 {

167 int bloom_fd = bpf_map__fd(bloom_map);

168 return bpf_map_update_elem(bloom_fd, NULL, &value, BPF_ANY);

169 }

170

171 References

172 ==========

173

174 https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/

175

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

Bloom filter map 특성과 설정

1-47

`BPF_MAP_TYPE_BLOOM_FILTER`는 `kernel version 5.16`에 도입되었습니다.

`BPF_MAP_TYPE_BLOOM_FILTER`는 BPF bloom filter map을 제공합니다. Bloom filter는 element가 set에 존재하는지 빠르게 검사하는 space-efficient probabilistic data structure입니다. False positive는 발생할 수 있지만 false negative는 발생하지 않습니다.

Bloom filter map에는 key가 없고 value만 있습니다. 생성할 때 `key_size`를 0으로 지정해야 하며 다음 두 operation을 지원합니다.

**push**: map에 element를 추가합니다.
**peek**: map에 element가 있는지 판정합니다.

BPF program은 element 추가에 `bpf_map_push_elem`, query에 `bpf_map_peek_elem`을 사용합니다. 기존 `bpf` syscall에서는 다음 userspace operation으로 노출됩니다.

`BPF_MAP_UPDATE_ELEM`은 push에 대응합니다.
`BPF_MAP_LOOKUP_ELEM`은 peek에 대응합니다.

Map 생성 시 지정하는 `max_entries`는 bloom filter의 합리적인 bitmap size를 추정하는 데 사용될 뿐 엄격한 entry limit으로 enforce되지 않습니다. `max_entries`보다 많은 entry를 넣을 수 있지만 false positive rate가 높아질 수 있습니다.

사용할 hash 수는 map 생성 시 `union bpf_attr`의 `map_extra` lower 4 bit로 설정합니다. 지정하지 않으면 기본값은 `5 hash functions`입니다. 일반적으로 hash 수를 늘리면 false positive rate가 낮아지는 대신 lookup speed도 낮아집니다.

Bloom filter map에서는 element를 delete할 수 없지만 inner map으로 사용할 수 있습니다. Concurrent update와 lookup에서도 false negative가 생기지 않도록 synchronization은 user가 책임져야 합니다.

Kernel BPF push와 peek helper

48-77

Bloom filter에 value를 추가하는 helper prototype은 다음과 같습니다.

long bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)

`bpf_map_push_elem()`에 entry를 추가할 때 `flags`는 반드시 `BPF_ANY`여야 합니다. 성공하면 0, 실패하면 negative error를 반환합니다.

Value의 존재 가능성을 검사하는 helper prototype은 다음과 같습니다.

long bpf_map_peek_elem(struct bpf_map *map, void *value)

`bpf_map_peek_elem()`은 value가 map에 아마 존재하면 0을 반환하고, 확실히 존재하지 않으면 `-ENOENT`를 반환합니다. 0은 probabilistic match이므로 실제 존재를 보장하지 않습니다.

Userspace update와 lookup API

78-105

Userspace에서 value를 push하는 libbpf API prototype은 다음과 같습니다.

int bpf_map_update_elem (int fd, const void *key, const void *value, __u64 flags)

`bpf_map_update_elem()`을 사용할 때 `key`는 `NULL`, `flags`는 `BPF_ANY`로 설정해야 합니다. 성공하면 0, 실패하면 negative error를 반환합니다.

Userspace에서 value의 존재 가능성을 검사하는 API prototype은 다음과 같습니다.

int bpf_map_lookup_elem (int fd, const void *key, void *value)

`bpf_map_lookup_elem()`의 `key`도 `NULL`이어야 합니다. Value가 아마 존재하면 0, 확실히 존재하지 않으면 `-ENOENT`를 반환합니다.

Kernel BPF 선언과 lookup 예제

106-138

다음 선언은 `__u32` value, `max_entries` 1000, `map_extra` 3개 hash를 사용하는 bloom filter를 `.maps` section에 만듭니다.

struct {
        __uint(type, BPF_MAP_TYPE_BLOOM_FILTER);
        __type(value, __u32);
        __uint(max_entries, 1000);
        __uint(map_extra, 3);
} bloom_filter SEC(".maps");

Lookup 예제는 먼저 `bpf_map_peek_elem()`로 key가 bloom filter에 있을 가능성을 검사합니다. 결과가 0이면 false positive인지 별도 hash table lookup으로 검증하면서 연결된 value를 가져옵니다.

void *lookup(__u32 key)
{
        if (bpf_map_peek_elem(&bloom_filter, &key) == 0) {
                /* Verify not a false positive and fetch an associated
                 * value using a secondary lookup, e.g. in a hash table
                 */
                return bpf_map_lookup_elem(&hash_table, &key);
        }
        return 0;
}

Userspace 생성과 element 추가 예제

139-170

Userspace 생성 예제는 `LIBBPF_OPTS(bpf_map_create_opts, ...)`로 `map_extra = 3`을 설정합니다. `bpf_map_create()`에는 type, name, 반드시 0인 key size, `ipv6_addr` value size, `max_entries` 10000, create option을 전달합니다.

int create_bloom()
{
        LIBBPF_OPTS(bpf_map_create_opts, opts,
                    .map_extra = 3);             /* number of hashes */

        return bpf_map_create(BPF_MAP_TYPE_BLOOM_FILTER,
                              "ipv6_bloom",      /* name */
                              0,                 /* key size, must be zero */
                              sizeof(ipv6_addr), /* value size */
                              10000,             /* max entries */
                              &opts);            /* create options */
}

Element 추가 예제는 `bpf_map__fd()`로 map fd를 얻은 뒤 `bpf_map_update_elem()`에 `NULL` key, value pointer, `BPF_ANY`를 전달합니다.

int add_element(struct bpf_map *bloom_map, __u32 value)
{
        int bloom_fd = bpf_map__fd(bloom_map);
        return bpf_map_update_elem(bloom_fd, NULL, &value, BPF_ANY);
}

Reference

171-174

[BPF bloom filter map patch discussion](https://lwn.net/ml/bpf/20210831225005.2762202-1-joannekoong@fb.com/)이 이 문서의 외부 reference입니다.