Large collection, best design

NTDEV
1

I want my kernel driver (WDM) to access a large collection (n < 10000, typically n > 1000) of strings for read-only purposes.

What is the best design to adopt?

Can this collection reside in memory?

In the registry?

Or should a file be accessed? Now let me be daring, a B-tree file?

2

Hi,

wrote in message news:xxxxx@ntdev…
>I want my kernel driver (WDM) to access a large collection (n < 10000,
>typically n > 1000) of strings for read-only purposes.
>
> What is the best design to adopt?

>
> Can this collection reside in memory?

What is the average length of the string ?
Depends, can you allow a pagefault in the search code path? or are you at
high irql?

You can try a bloom filter residing in the driver non paged memory connected
to a bigger hash code table in user space?

>
> In the registry?
>
> Or should a file be accessed? Now let me be daring, a B-tree file?

My guess is that it would be overkill for 0>
>
hope this help.

J.

3

It’s a two part question… The first is how to efficiently use memory to store the strings. Are they all close to the same size? Are the strings ever accessed by routines running at DISPATCH_LEVEL or >? Do the strings come and go? Or are they loaded up once and then just retrieved at times?

4

> Can this collection reside in memory?

1MB? I think yes.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

5

Who said the strings were 100 bytes :wink:

6

> Who said the strings were 100 bytes :wink:

The off-the-head sane approach :slight_smile:

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

7

Hard to say without more details of the nature of the strings, their
lifetime and how you are going to use them, but if you do decide to go a
tree route, the kernel already has support for AVL trees:

http://msdn.microsoft.com/en-us/library/ff553024(VS.85).aspx

You’ll need to put this define before you include ‘ntrtl.h’

#define RTL_USE_AVL_TABLES 0

I’m in no way saying at this point that this would be a good fit for what
you wish to do. , but should the details fit with this, I thought I’d
include the information.

Good luck,

mm

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Maxim S. Shatskih
Sent: Thursday, October 14, 2010 10:24 PM
To: Windows System Software Devs Interest List
Subject: Re:[ntdev] Large collection, best design

Who said the strings were 100 bytes :wink:

The off-the-head sane approach :slight_smile:

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer