Merge pull request #948 from shodoco/master
bcc: add support for lpm trie map type
diff --git a/docs/kernel-versions.md b/docs/kernel-versions.md
index 896f83f..462ff7d 100644
--- a/docs/kernel-versions.md
+++ b/docs/kernel-versions.md
@@ -54,10 +54,11 @@
Per-CPU hash | 4.6 | [824bd0ce6c7c](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=824bd0ce6c7c43a9e1e210abf124958e54d88342)
Per-CPU array | 4.6 | [a10423b87a7e](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=a10423b87a7eae75da79ce80a8d9475047a674ee)
Stack trace | 4.6 | [d5a3b1f69186](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=d5a3b1f691865be576c2bffa708549b8cdccda19)
-Pre-alloc maps memory | 4.6 | [6c90598174322](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=6c90598174322b8888029e40dd84a4eb01f56afe)
+Pre-alloc maps memory | 4.6 | [6c9059817432](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=6c90598174322b8888029e40dd84a4eb01f56afe)
cgroup array | 4.8 | [4ed8ec521ed5](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=4ed8ec521ed57c4e207ad464ca0388776de74d4b)
-LRU hash | [4.10](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=29ba732acbeece1e34c68483d1ec1f3720fa1bb3) | [](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=29ba732acbeece1e34c68483d1ec1f3720fa1bb3)
-LRU per-CPU hash | [4.10](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=8f8449384ec364ba2a654f11f94e754e4ff719e0) | [](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=8f8449384ec364ba2a654f11f94e754e4ff719e0)
+LRU hash | 4.10 | [29ba732acbee](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=29ba732acbeece1e34c68483d1ec1f3720fa1bb3)
+LRU per-CPU hash | 4.10 | [8f8449384ec3](https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=8f8449384ec364ba2a654f11f94e754e4ff719e0)
+LPM trie | 4.11 | [b95a5c4db09b](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=b95a5c4db09bc7c253636cb84dc9b12c577fd5a0)
Text string | _To be done?_ |
Variable-length maps | _To be done?_ |
diff --git a/src/cc/compat/linux/bpf.h b/src/cc/compat/linux/bpf.h
index e7bb296..8d6dd1d 100644
--- a/src/cc/compat/linux/bpf.h
+++ b/src/cc/compat/linux/bpf.h
@@ -63,6 +63,12 @@
__s32 imm; /* signed immediate constant */
};
+/* Key of an a BPF_MAP_TYPE_LPM_TRIE entry */
+struct bpf_lpm_trie_key {
+ __u32 prefixlen; /* up to 32 for AF_INET, 128 for AF_INET6 */
+ __u8 data[0]; /* Arbitrary size */
+};
+
/* BPF syscall commands, see bpf(2) man-page for details. */
enum bpf_cmd {
BPF_MAP_CREATE,
@@ -89,6 +95,7 @@
BPF_MAP_TYPE_CGROUP_ARRAY,
BPF_MAP_TYPE_LRU_HASH,
BPF_MAP_TYPE_LRU_PERCPU_HASH,
+ BPF_MAP_TYPE_LPM_TRIE,
};
enum bpf_prog_type {
diff --git a/src/cc/compat/linux/virtual_bpf.h b/src/cc/compat/linux/virtual_bpf.h
index 05348ff..107a175 100644
--- a/src/cc/compat/linux/virtual_bpf.h
+++ b/src/cc/compat/linux/virtual_bpf.h
@@ -64,6 +64,12 @@
__s32 imm; /* signed immediate constant */
};
+/* Key of an a BPF_MAP_TYPE_LPM_TRIE entry */
+struct bpf_lpm_trie_key {
+ __u32 prefixlen; /* up to 32 for AF_INET, 128 for AF_INET6 */
+ __u8 data[0]; /* Arbitrary size */
+};
+
/* BPF syscall commands, see bpf(2) man-page for details. */
enum bpf_cmd {
BPF_MAP_CREATE,
@@ -90,6 +96,7 @@
BPF_MAP_TYPE_CGROUP_ARRAY,
BPF_MAP_TYPE_LRU_HASH,
BPF_MAP_TYPE_LRU_PERCPU_HASH,
+ BPF_MAP_TYPE_LPM_TRIE,
};
enum bpf_prog_type {
diff --git a/src/cc/frontends/clang/b_frontend_action.cc b/src/cc/frontends/clang/b_frontend_action.cc
index 3b63367..534b66a 100644
--- a/src/cc/frontends/clang/b_frontend_action.cc
+++ b/src/cc/frontends/clang/b_frontend_action.cc
@@ -645,6 +645,8 @@
map_type = BPF_MAP_TYPE_LRU_HASH;
} else if (A->getName() == "maps/lru_percpu_hash") {
map_type = BPF_MAP_TYPE_LRU_PERCPU_HASH;
+ } else if (A->getName() == "maps/lpm_trie") {
+ map_type = BPF_MAP_TYPE_LPM_TRIE;
} else if (A->getName() == "maps/histogram") {
if (table.key_desc == "\"int\"")
map_type = BPF_MAP_TYPE_ARRAY;
diff --git a/src/lua/bcc/table.lua b/src/lua/bcc/table.lua
index 767402c..c01f006 100644
--- a/src/lua/bcc/table.lua
+++ b/src/lua/bcc/table.lua
@@ -29,6 +29,7 @@
BaseTable.static.BPF_MAP_TYPE_CGROUP_ARRAY = 8
BaseTable.static.BPF_MAP_TYPE_LRU_HASH = 9
BaseTable.static.BPF_MAP_TYPE_LRU_PERCPU_HASH = 10
+BaseTable.static.BPF_MAP_TYPE_LPM_TRIE = 11
function BaseTable:initialize(t_type, bpf, map_id, map_fd, key_type, leaf_type)
assert(t_type == libbcc.bpf_table_type_id(bpf.module, map_id))
diff --git a/src/lua/bpf/cdef.lua b/src/lua/bpf/cdef.lua
index d7be776..c26ff1c 100644
--- a/src/lua/bpf/cdef.lua
+++ b/src/lua/bpf/cdef.lua
@@ -140,6 +140,7 @@
S.c.BPF_MAP.CGROUP_ARRAY = 8
S.c.BPF_MAP.LRU_HASH = 9
S.c.BPF_MAP.LRU_PERCPU_HASH = 10
+ S.c.BPF_MAP.LPM_TRIE = 11
end
if not S.c.BPF_PROG.TRACEPOINT then
S.c.BPF_PROG.TRACEPOINT = 5
diff --git a/src/python/bcc/table.py b/src/python/bcc/table.py
index b6feff2..bb4cd41 100644
--- a/src/python/bcc/table.py
+++ b/src/python/bcc/table.py
@@ -34,6 +34,7 @@
BPF_MAP_TYPE_CGROUP_ARRAY = 8
BPF_MAP_TYPE_LRU_HASH = 9
BPF_MAP_TYPE_LRU_PERCPU_HASH = 10
+BPF_MAP_TYPE_LPM_TRIE = 11
stars_max = 40
log2_index_max = 65
@@ -124,6 +125,8 @@
t = PerCpuHash(bpf, map_id, map_fd, keytype, leaftype, **kwargs)
elif ttype == BPF_MAP_TYPE_PERCPU_ARRAY:
t = PerCpuArray(bpf, map_id, map_fd, keytype, leaftype, **kwargs)
+ elif ttype == BPF_MAP_TYPE_LPM_TRIE:
+ t = LpmTrie(bpf, map_id, map_fd, keytype, leaftype)
elif ttype == BPF_MAP_TYPE_STACK_TRACE:
t = StackTrace(bpf, map_id, map_fd, keytype, leaftype)
elif ttype == BPF_MAP_TYPE_LRU_HASH:
@@ -665,6 +668,18 @@
result = self.sum(key)
return result.value / self.total_cpu
+class LpmTrie(TableBase):
+ def __init__(self, *args, **kwargs):
+ super(LpmTrie, self).__init__(*args, **kwargs)
+
+ def __len__(self):
+ raise NotImplementedError
+
+ def __delitem__(self, key):
+ # Not implemented for lpm trie as of kernel commit
+ # b95a5c4db09bc7c253636cb84dc9b12c577fd5a0
+ raise NotImplementedError
+
class StackTrace(TableBase):
MAX_DEPTH = 127
diff --git a/tests/python/test_lpm_trie.py b/tests/python/test_lpm_trie.py
new file mode 100644
index 0000000..4fdb982
--- /dev/null
+++ b/tests/python/test_lpm_trie.py
@@ -0,0 +1,74 @@
+#!/usr/bin/env python
+# Copyright (c) 2017 Facebook, Inc.
+# Licensed under the Apache License, Version 2.0 (the "License")
+
+import ctypes as ct
+import unittest
+from bcc import BPF
+from netaddr import IPAddress
+
+class KeyV4(ct.Structure):
+ _fields_ = [("prefixlen", ct.c_uint),
+ ("data", ct.c_ubyte * 4)]
+
+class KeyV6(ct.Structure):
+ _fields_ = [("prefixlen", ct.c_uint),
+ ("data", ct.c_ushort * 8)]
+
+class TestLpmTrie(unittest.TestCase):
+ def test_lpm_trie_v4(self):
+ test_prog1 = """
+ BPF_F_TABLE("lpm_trie", u64, int, trie, 16, BPF_F_NO_PREALLOC);
+ """
+ b = BPF(text=test_prog1)
+ t = b["trie"]
+
+ k1 = KeyV4(24, (192, 168, 0, 0))
+ v1 = ct.c_int(24)
+ t[k1] = v1
+
+ k2 = KeyV4(28, (192, 168, 0, 0))
+ v2 = ct.c_int(28)
+ t[k2] = v2
+
+ k = KeyV4(32, (192, 168, 0, 15))
+ self.assertEqual(t[k].value, 28)
+
+ k = KeyV4(32, (192, 168, 0, 127))
+ self.assertEqual(t[k].value, 24)
+
+ with self.assertRaises(KeyError):
+ k = KeyV4(32, (172, 16, 1, 127))
+ v = t[k]
+
+ def test_lpm_trie_v6(self):
+ test_prog1 = """
+ struct key_v6 {
+ u32 prefixlen;
+ u32 data[4];
+ };
+ BPF_F_TABLE("lpm_trie", struct key_v6, int, trie, 16, BPF_F_NO_PREALLOC);
+ """
+ b = BPF(text=test_prog1)
+ t = b["trie"]
+
+ k1 = KeyV6(64, IPAddress('2a00:1450:4001:814:200e::').words)
+ v1 = ct.c_int(64)
+ t[k1] = v1
+
+ k2 = KeyV6(96, IPAddress('2a00:1450:4001:814::200e').words)
+ v2 = ct.c_int(96)
+ t[k2] = v2
+
+ k = KeyV6(128, IPAddress('2a00:1450:4001:814::1024').words)
+ self.assertEqual(t[k].value, 96)
+
+ k = KeyV6(128, IPAddress('2a00:1450:4001:814:2046::').words)
+ self.assertEqual(t[k].value, 64)
+
+ with self.assertRaises(KeyError):
+ k = KeyV6(128, IPAddress('2a00:ffff::').words)
+ v = t[k]
+
+if __name__ == "__main__":
+ unittest.main()