Choosing Between Adaptive Radix Trie and PREFIX_TABLE for Storing File Paths in a Minifilter Driver

NTFSD
1

Hello everyone,

I want to store file paths with associated access rights in a minifilter driver. I’ve been comparing two data structures:

  • Adaptive Radix Trie (ART): Dynamically adapts the node size for better cache locality and memory efficiency. It includes path compression (skipping over nodes with single children).
  • PREFIX_TABLE: Has a fixed structure and does not compress paths, reflecting the file system hierarchy directly.

While ART generally offers higher performance, the PREFIX_TABLE is a kernel-specific data structure designed for managing file system object prefixes (like path-based lookups).

I’m unsure which one would be more suitable for a minifilter driver. Since this minifilter is for a commercial product and must be signed by Windows, I’m particularly interested in knowing which implementation is more acceptable or recommended for Windows kernel development.

Any insights or best practices would be appreciated!

Thank you.

2

What is there that is not acceptable in either?
Pick the faster one.

IMO tries are not efficient for this, if the number of entries is high (we had like 1000+ and trie implementation we did was awful.
Hashing proved the most efficient.
I doubt you'd ask or care if you only had like 10-50 paths..

But test your sample paths! The only wrong implentation guaranteed is an untested one!

3

There aren't really any driver specific considerations here. Unless you are thinking of using some library that implements a trie, to make sure that I can be used in KM.

The choice of data structure is governed by your access patterns (insert, update, delete, lookup), the thread sync you need, and memory limitations. Start with the expected size of the data you need to store, and the ratio between the different accesses. That should tell you about the thread sync and memory. And then you can choose something