3461793179

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/google/santa/commit/<a class=hub.com/google/santa/commit/<a class="double-link" href="https://git"><a class=hub.com/google/santa/commit/<a class="double-link" href="https://git"><a class=hub.com/google/santa/commit/<a class="double-link" href="https://git"><a class=hub.com/google/santa/commit/ee86014d24c7b5b3d696f0ae25243b8b061add17">ee86014d2">&lt;a href=&quot;https://github.com/google/santa/commit/</a><a class="double-link" href="https://github.com/google/santa/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/santa/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/santa/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/santa/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/santa/commit/ee86014d24c7b5b3d696f0ae25243b8b061add17">ee86014d2</a><a href="https://github.com/google/santa/commit/ee86014d24c7b5b3d696f0ae25243b8b061add17">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/google/santa/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/google/santa/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/santa/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/santa/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/santa/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/santa/commit/ee86014d24c7b5b3d696f0ae25243b8b061add17&quot;&gt;ee86014d2&lt;/a&gt;&lt;a href=&quot;https://github.com/google/santa/commit/ee86014d24c7b5b3d696f0ae25243b8b061add17&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/google/santa/commit/&amp;lt;/a&amp;gt;&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://github.com/google/santa/commit/&amp;amp;lt;a class=&amp;amp;quot;double-link&amp;amp;quot; href=&amp;amp;quot;https://git&amp;quot... (continued)

Pull Request Pull Request #931: Prefix tree updates

Run Details

3071 of 6528 branches covered (47.04%)

Branch coverage included in aggregate %.

256 of 256 new or added lines in 5 files covered. (100.0%)

11325 of 16272 relevant lines covered (69.6%)

17173.13 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.5

/Source/common/PrefixTree.h

/// Copyright 2022 Google LLC
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
///     https://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.

#ifndef SANTA__COMMON__PREFIXTREE_H
#define SANTA__COMMON__PREFIXTREE_H

#include <sys/syslimits.h>

#include <optional>

#import "Source/common/SNTLogging.h"
#include "absl/synchronization/mutex.h"

#if SANTA_PREFIX_TREE_DEBUG
#define DEBUG_LOG LOGD
#else
#define DEBUG_LOG(format, ...)  // NOP
#endif

namespace santa::common {

template <typename ValueT>
class PrefixTree {
 private:
  // Forward declaration
  enum class NodeType;
  class TreeNode;

 public:
  PrefixTree(uint32_t max_depth = PATH_MAX)
      : root_(new TreeNode()), max_depth_(max_depth), node_count_(0) {}

  ~PrefixTree() { PruneLocked(root_); }

  bool InsertPrefix(const char *s, ValueT value) {
    absl::MutexLock lock(&lock_);
    return InsertLocked(s, value, NodeType::kPrefix);
  }

  bool InsertLiteral(const char *s, ValueT value) {
    absl::MutexLock lock(&lock_);
    return InsertLocked(s, value, NodeType::kLiteral);
  }

  bool HasPrefix(const char *input) {
    absl::ReaderMutexLock lock(&lock_);
    return HasPrefixLocked(input);
  }

  std::optional<ValueT> LookupLongestMatchingPrefix(const char *input) {
    absl::ReaderMutexLock lock(&lock_);
    return LookupLongestMatchingPrefixLocked(input);
  }

  void Reset() {
    absl::MutexLock lock(&lock_);
    PruneLocked(root_);
    root_ = new TreeNode();
    node_count_ = 0;
  }

#if SANTA_PREFIX_TREE_DEBUG
  void Print() {
    char buf[max_depth_ + 1];
    memset(buf, 0, sizeof(buf));

    absl::ReaderMutexLock lock(&lock_);
    PrintLocked(root_, buf, 0);
  }

  uint32_t NodeCount() {
    absl::ReaderMutexLock lock(&lock_);
    return node_count_;
  }
#endif

 private:
  ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_)
  bool InsertLocked(const char *input, ValueT value, NodeType node_type) {
    const char *p = input;
    TreeNode *node = root_;

    while (*p) {
      uint8_t cur_byte = (uint8_t)*p;

      TreeNode *child_node = node->children_[cur_byte];
      if (!child_node) {
        // Current node doesn't exist...
        // Create the rest of the nodes in the tree for the given string

        // Keep a pointer to where this new branch starts from. If the
        // input length exceeds max_depth, the new branch will need to
        // be pruned.
        TreeNode *branch_start_node = node;
        uint8_t branch_start_byte = (uint8_t)*p;

        do {
          TreeNode *new_node = new TreeNode();
          node->children_[cur_byte] = new_node;
          node = new_node;
          node_count_++;

          // Check current depth...
          if (p - input >= max_depth_) {
            // Attempted to add a string that exceeded max depth
            // Prune tree from start of this new branch
            PruneLocked(branch_start_node->children_[branch_start_byte]);
            branch_start_node->children_[branch_start_byte] = nullptr;

            return false;
          }

          cur_byte = (uint8_t) * ++p;
        } while (*p);

        node->node_type_ = node_type;
        node->value_ = value;

        return true;
      } else if (*(p + 1) == '\0') {
        // Current node exists and we're at the end of our input...
        // Note: The current node's data will be overwritten

        // Only increment node count if the previous node type wasn't already a
        // prefix or literal type (in which case it was already counted)
        if (child_node->node_type_ == NodeType::kInner) {
          node_count_++;
        }

        child_node->node_type_ = node_type;
        child_node->value_ = value;
        return true;
      }

      node = child_node;
      p++;
    }

    // Should only get here when input is an empty string
    return false;
  }

  ABSL_SHARED_LOCKS_REQUIRED(lock_)
  bool HasPrefixLocked(const char *input) {
    TreeNode *node = root_;
    const char *p = input;

    while (*p) {
      node = node->children_[(uint8_t)*p++];

      if (!node) {
        break;
      }

      if (node->node_type_ == NodeType::kPrefix ||
          (*p == '\0' && node->node_type_ == NodeType::kLiteral)) {
        return true;
      }
    }

    return false;
  }

  ABSL_SHARED_LOCKS_REQUIRED(lock_)
  std::optional<ValueT> LookupLongestMatchingPrefixLocked(const char *input) {
    TreeNode *node = root_;
    TreeNode *match = nullptr;
    const char *p = input;

    while (*p) {
      node = node->children_[(uint8_t)*p++];

      if (!node) {
        break;
      }

      if (node->node_type_ == NodeType::kPrefix ||
          (*p == '\0' && node->node_type_ == NodeType::kLiteral)) {
        match = node;
      }
    }

    return match ? std::make_optional<ValueT>(match->value_) : std::nullopt;
  }

  ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_)
  void PruneLocked(TreeNode *target) {
    if (!target) {
      return;
    }

    // For deep trees, a recursive approach will generate too many stack frames.
    // Since the depth of the tree is configurable, err on the side of caution
    // and use a "stack" to walk the tree in a non-recursive manner.
    TreeNode **stack = new TreeNode *[node_count_ + 1];
    if (!stack) {
      LOGE(@"Unable to prune tree!");
      return;
    }

    uint32_t count = 0;

    // Seed the "stack" with a starting node.
    stack[count++] = target;

    // Start at the target node and walk the tree to find and delete all the
    // sub-nodes.
    while (count) {
      TreeNode *node = stack[--count];

      for (int i = 0; i < 256; ++i) {
        if (!node->children_[i]) {
          continue;
        }
        stack[count++] = node->children_[i];
      }

      delete node;
      --node_count_;
    }

    delete[] stack;
  }

#if SANTA_PREFIX_TREE_DEBUG
  ABSL_SHARED_LOCKS_REQUIRED(lock_)
  void PrintLocked(TreeNode *node, char *buf, uint32_t depth) {
    for (size_t i = 0; i < 256; i++) {
      TreeNode *cur_node = node->children_[i];
      if (cur_node) {
        buf[depth] = i;
        if (cur_node->node_type_ != NodeType::kInner) {
          printf("\t%s (type: %s)\n", buf,
                 cur_node->node_type_ == NodeType::kPrefix ? "prefix" : "literal");
        }
        PrintLocked(cur_node, buf, depth + 1);
        buf[depth] = '\0';
      }
    }
  }
#endif

  enum class NodeType {
    kInner = 0,
    kPrefix,
    kLiteral,
  };

  ///
  ///  TreeNode is a wrapper class that represents one byte.
  ///  1 node can represent a whole ASCII character.
  ///  For example a pointer to the 'A' node will be stored at children[0x41].
  ///  It takes 1-4 nodes to represent a UTF-8 encoded Unicode character.
  ///
  ///  The path for "/🤘" would look like this:
  ///      children[0x2f] -> children[0xf0] -> children[0x9f] -> children[0xa4]
  ///      -> children[0x98]
  ///
  ///  The path for "/dev" is:
  ///      children[0x2f] -> children[0x64] -> children[0x65] -> children[0x76]
  ///
  ///  Lookups of children are O(1).
  ///
  ///  Having the nodes represented by a smaller width, such as a nibble (1/2
  ///  byte), would drastically decrease the memory footprint but would double
  ///  required dereferences.
  ///
  ///  TODO(bur): Potentially convert this into a full on radix tree.
  ///
  class TreeNode {
   public:
    TreeNode() : children_(), node_type_(NodeType::kInner) {}
    ~TreeNode() = default;
    TreeNode *children_[256];
    PrefixTree::NodeType node_type_;
    ValueT value_;
  };

  TreeNode *root_;
  const uint32_t max_depth_;
  uint32_t node_count_ ABSL_GUARDED_BY(lock_);
  absl::Mutex lock_;
};

}  // namespace santa::common

#endif

1	/// Copyright 2022 Google LLC
2	///
3	/// Licensed under the Apache License, Version 2.0 (the "License");
4	/// you may not use this file except in compliance with the License.
5	/// You may obtain a copy of the License at
6	///
7	/// https://www.apache.org/licenses/LICENSE-2.0
8	///
9	/// Unless required by applicable law or agreed to in writing, software
10	/// distributed under the License is distributed on an "AS IS" BASIS,
11	/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12	/// See the License for the specific language governing permissions and
13	/// limitations under the License.
14
15	#ifndef SANTA__COMMON__PREFIXTREE_H
16	#define SANTA__COMMON__PREFIXTREE_H
17
18	#include <sys/syslimits.h>
19
20	#include <optional>
21
22	#import "Source/common/SNTLogging.h"
23	#include "absl/synchronization/mutex.h"
24
25	#if SANTA_PREFIX_TREE_DEBUG
26	#define DEBUG_LOG LOGD
27	#else
28	#define DEBUG_LOG(format, ...) // NOP
29	#endif
30
31	namespace santa::common {
32
33	template <typename ValueT>
34	class PrefixTree {
35	private:
36	// Forward declaration
37	enum class NodeType;
38	class TreeNode;
39
40	public:
41	PrefixTree(uint32_t max_depth = PATH_MAX)
42	: root_(new TreeNode()), max_depth_(max_depth), node_count_(0) {}	22✔
43
44	~PrefixTree() { PruneLocked(root_); }	21✔
45
46	bool InsertPrefix(const char *s, ValueT value) {	4,144✔
47	absl::MutexLock lock(&lock_);	4,144✔
48	return InsertLocked(s, value, NodeType::kPrefix);	4,144✔
49	}	4,144✔
50
51	bool InsertLiteral(const char *s, ValueT value) {	9✔
52	absl::MutexLock lock(&lock_);	9✔
53	return InsertLocked(s, value, NodeType::kLiteral);	9✔
54	}	9✔
55
56	bool HasPrefix(const char *input) {	598,638✔
57	absl::ReaderMutexLock lock(&lock_);	598,638✔
58	return HasPrefixLocked(input);	598,638✔
59	}	598,638✔
60
61	std::optional<ValueT> LookupLongestMatchingPrefix(const char *input) {	8✔
62	absl::ReaderMutexLock lock(&lock_);	8✔
63	return LookupLongestMatchingPrefixLocked(input);	8✔
64	}	8✔
65
66	void Reset() {	2✔
67	absl::MutexLock lock(&lock_);	2✔
68	PruneLocked(root_);	2✔
69	root_ = new TreeNode();	2✔
70	node_count_ = 0;	2✔
71	}	2✔
72
73	#if SANTA_PREFIX_TREE_DEBUG
74	void Print() {
75	char buf[max_depth_ + 1];
76	memset(buf, 0, sizeof(buf));
77
78	absl::ReaderMutexLock lock(&lock_);
79	PrintLocked(root_, buf, 0);
80	}
81
82	uint32_t NodeCount() {	9✔
83	absl::ReaderMutexLock lock(&lock_);	9✔
84	return node_count_;	9✔
85	}	9✔
86	#endif
87
88	private:
89	ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_)
90	bool InsertLocked(const char *input, ValueT value, NodeType node_type) {	4,154✔
91	const char *p = input;	4,154✔
92	TreeNode *node = root_;	4,154✔
93
94	while (*p) {	13,782!
95	uint8_t cur_byte = (uint8_t)*p;	13,780✔
96
97	TreeNode *child_node = node->children_[cur_byte];	13,780✔
98	if (!child_node) {	13,780!
99	// Current node doesn't exist...
100	// Create the rest of the nodes in the tree for the given string
101
102	// Keep a pointer to where this new branch starts from. If the
103	// input length exceeds max_depth, the new branch will need to
104	// be pruned.
105	TreeNode *branch_start_node = node;	4,143✔
106	uint8_t branch_start_byte = (uint8_t)*p;	4,143✔
107
108	do {	138,143✔
109	TreeNode *new_node = new TreeNode();	138,143✔
110	node->children_[cur_byte] = new_node;	138,143✔
111	node = new_node;	138,143✔
112	node_count_++;	138,143✔
113
114	// Check current depth...
115	if (p - input >= max_depth_) {	138,143!
116	// Attempted to add a string that exceeded max depth
117	// Prune tree from start of this new branch
118	PruneLocked(branch_start_node->children_[branch_start_byte]);	1✔
119	branch_start_node->children_[branch_start_byte] = nullptr;	1✔
120
121	return false;	1✔
122	}	1✔
123
124	cur_byte = (uint8_t) * ++p;	138,142✔
125	} while (*p);	138,142✔
126
127	node->node_type_ = node_type;	4,142✔
128	node->value_ = value;	4,142✔
129
130	return true;	4,142✔
131	} else if (*(p + 1) == '\0') {	9,637!
132	// Current node exists and we're at the end of our input...
133	// Note: The current node's data will be overwritten
134
135	// Only increment node count if the previous node type wasn't already a
136	// prefix or literal type (in which case it was already counted)
137	if (child_node->node_type_ == NodeType::kInner) {	9!
138	node_count_++;	2✔
139	}	2✔
140
141	child_node->node_type_ = node_type;	9✔
142	child_node->value_ = value;	9✔
143	return true;	9✔
144	}	9✔
145
146	node = child_node;	9,628✔
147	p++;	9,628✔
148	}	9,628✔
149
150	// Should only get here when input is an empty string
151	return false;	2✔
152	}	4,154✔
153
154	ABSL_SHARED_LOCKS_REQUIRED(lock_)
155	bool HasPrefixLocked(const char *input) {	601,687✔
156	TreeNode *node = root_;	601,687✔
157	const char *p = input;	601,687✔
158
159	while (*p) {	19,668,850✔
160	node = node->children_[(uint8_t)*p++];	19,668,495✔
161
162	if (!node) {	19,668,495✔
163	break;	15✔
164	}	15✔
165
166	if (node->node_type_ == NodeType::kPrefix \|\|	19,668,480✔
167	(*p == '\0' && node->node_type_ == NodeType::kLiteral)) {	18,869,012!
168	return true;	601,317✔
169	}	601,317✔
170	}	19,668,480✔
171
172	return false;	370✔
173	}	601,687✔
174
175	ABSL_SHARED_LOCKS_REQUIRED(lock_)
176	std::optional<ValueT> LookupLongestMatchingPrefixLocked(const char *input) {	8✔
177	TreeNode *node = root_;	8✔
178	TreeNode *match = nullptr;	8✔
179	const char *p = input;	8✔
180
181	while (*p) {	47✔
182	node = node->children_[(uint8_t)*p++];	43✔
183
184	if (!node) {	43✔
185	break;	4✔
186	}	4✔
187
188	if (node->node_type_ == NodeType::kPrefix \|\|	39✔
189	(*p == '\0' && node->node_type_ == NodeType::kLiteral)) {	32!
190	match = node;	7✔
191	}	7✔
192	}	39✔
193
194	return match ? std::make_optional<ValueT>(match->value_) : std::nullopt;	6✔
195	}	8✔
196
197	ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_)
198	void PruneLocked(TreeNode *target) {	24✔
199	if (!target) {	24!
200	return;	×
201	}	×
202
203	// For deep trees, a recursive approach will generate too many stack frames.
204	// Since the depth of the tree is configurable, err on the side of caution
205	// and use a "stack" to walk the tree in a non-recursive manner.
206	TreeNode *stack = new TreeNode [node_count_ + 1];	24✔
207	if (!stack) {	24!
208	LOGE(@"Unable to prune tree!");	×
209	return;	×
210	}	×
211
212	uint32_t count = 0;	24✔
213
214	// Seed the "stack" with a starting node.
215	stack[count++] = target;	24✔
216
217	// Start at the target node and walk the tree to find and delete all the
218	// sub-nodes.
219	while (count) {	298✔
220	TreeNode *node = stack[--count];	274✔
221
222	for (int i = 0; i < 256; ++i) {	70,418✔
223	if (!node->children_[i]) {	70,144✔
224	continue;	69,894✔
225	}	69,894✔
226	stack[count++] = node->children_[i];	250✔
227	}	250✔
228
229	delete node;	274✔
230	--node_count_;	274✔
231	}	274✔
232
233	delete[] stack;	24✔
234	}	24✔
235
236	#if SANTA_PREFIX_TREE_DEBUG
237	ABSL_SHARED_LOCKS_REQUIRED(lock_)
238	void PrintLocked(TreeNode node, char buf, uint32_t depth) {
239	for (size_t i = 0; i < 256; i++) {
240	TreeNode *cur_node = node->children_[i];
241	if (cur_node) {
242	buf[depth] = i;
243	if (cur_node->node_type_ != NodeType::kInner) {
244	printf("\t%s (type: %s)\n", buf,
245	cur_node->node_type_ == NodeType::kPrefix ? "prefix" : "literal");
246	}
247	PrintLocked(cur_node, buf, depth + 1);
248	buf[depth] = '\0';
249	}
250	}
251	}
252	#endif
253
254	enum class NodeType {
255	kInner = 0,
256	kPrefix,
257	kLiteral,
258	};
259
260	///
261	/// TreeNode is a wrapper class that represents one byte.
262	/// 1 node can represent a whole ASCII character.
263	/// For example a pointer to the 'A' node will be stored at children[0x41].
264	/// It takes 1-4 nodes to represent a UTF-8 encoded Unicode character.
265	///
266	/// The path for "/🤘" would look like this:
267	/// children[0x2f] -> children[0xf0] -> children[0x9f] -> children[0xa4]
268	/// -> children[0x98]
269	///
270	/// The path for "/dev" is:
271	/// children[0x2f] -> children[0x64] -> children[0x65] -> children[0x76]
272	///
273	/// Lookups of children are O(1).
274	///
275	/// Having the nodes represented by a smaller width, such as a nibble (1/2
276	/// byte), would drastically decrease the memory footprint but would double
277	/// required dereferences.
278	///
279	/// TODO(bur): Potentially convert this into a full on radix tree.
280	///
281	class TreeNode {
282	public:
283	TreeNode() : children_(), node_type_(NodeType::kInner) {}	138,167✔
284	~TreeNode() = default;	7✔
285	TreeNode *children_[256];
286	PrefixTree::NodeType node_type_;
287	ValueT value_;
288	};
289
290	TreeNode *root_;
291	const uint32_t max_depth_;
292	uint32_t node_count_ ABSL_GUARDED_BY(lock_);
293	absl::Mutex lock_;
294	};
295
296	} // namespace santa::common
297
298	#endif

google / santa / 3461793179

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous