Hi All,
As I am new to driver development as
there any way to implement HashMapping mechanism in my driver.
As i wanted map for process id’s and its some information.
I have tried simple link list but its not that much effective.
Thanks
The sad answer is that, even though this is 2015, you have to write your own.
The good news is that, because you get to write your own, it will be specifically tailored to your needs and will thus (if you do a good job) outperform many generic hash packages you might otherwise use because they’re easy.
If, instead of a HASH package specifically, you want a table package, there *are* a set of built-in table functions available in kernel-mode. This includes both splay tree and Red Black trees. Google RTL generic table for info.
Peter
OSR
@OSRDrivers
Red/Black or AVL?
ᐧ
On Mon, Jun 8, 2015 at 8:25 AM, wrote:
>
>
> The sad answer is that, even though this is 2015, you have to write your
> own.
>
> The good news is that, because you get to write your own, it will be
> specifically tailored to your needs and will thus (if you do a good job)
> outperform many generic hash packages you might otherwise use because
> they’re easy.
>
> If, instead of a HASH package specifically, you want a table package,
> there are a set of built-in table functions available in kernel-mode.
> This includes both splay tree and Red Black trees. Google RTL generic
> table for info.
>
> Peter
> OSR
> @OSRDrivers
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
–
Jamey Kirby
Disrupting the establishment since 1964
This is a personal email account and as such, emails are not subject to
archiving. Nothing else really matters.
xxxxx@gmail.com wrote:
As I am new to driver development as
there any way to implement HashMapping mechanism in my driver.
As i wanted map for process id’s and its some information.
I have tried simple link list but its not that much effective.
What do you mean by “not that much effective”? There is something to be
said for simplicity. Simple code that works is better than complicated
code that doesn’t, even if it takes a little more time. How often are
you traversing the list? If it takes a little longer but you only scan
the list once a second, then who cares?
–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.
You are correct, Mr. Kirby. It *is* AVL… the “all new and improved” Red/Black tree 
Peter
OSR
@OSRDrivers
I am going to go a little off-topic here, but not too much. I have been
reading this today. An fantastic read. Don’t skip section 2.2…
http://judy.sourceforge.net/doc/shop_interm.pdf
ᐧ
On Mon, Jun 8, 2015 at 5:58 PM, wrote:
>
>
> You are correct, Mr. Kirby. It is AVL… the “all new and improved”
> Red/Black tree
>
> Peter
> OSR
> @OSRDrivers
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
–
Jamey Kirby
Disrupting the establishment since 1964
This is a personal email account and as such, emails are not subject to
archiving. Nothing else really matters.
I saw this back in 2010, and I had contacted him several time over the email. It is (Judy tree) and interesting implementation. Usually I don’t look at source code, unless I get into trouble. Here of course I had trouble, and so I remember it. It does have recursive calls in few places, and the code is not much readable, perhaps due to optimization, but I asked why he wrote this way. He said he wanted to change it to refactor and people to understand it better, but due to its becoming open source, he was advised not to change.
That recursion had to be tackled based on what os version one is dealing with. So it was mix of things that made it not to work as “as is” in windows kernel :-).
-Pro
On Jun 8, 2015, at 8:37 PM, Jamey Kirby wrote:
> I am going to go a little off-topic here, but not too much. I have been reading this today. An fantastic read. Don’t skip section 2.2…
>
> http://judy.sourceforge.net/doc/shop_interm.pdf
>
> ᐧ
>
> On Mon, Jun 8, 2015 at 5:58 PM, wrote:
>
>
> You are correct, Mr. Kirby. It is AVL… the “all new and improved” Red/Black tree
>
> Peter
> OSR
> @OSRDrivers
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
>
>
>
> –
> Jamey Kirby
> Disrupting the establishment since 1964
>
> This is a personal email account and as such, emails are not subject to archiving. Nothing else really matters.
> — NTDEV is sponsored by OSR Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev OSR is HIRING!! See http://www.osr.com/careers 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
Rtl (at least in Win 8.1) has distinct AVL, RB and HashTable implementations.
AVL is since XP
–
Maxim S. Shatskih
Microsoft MVP on File System And Storage
xxxxx@storagecraft.com
http://www.storagecraft.com
wrote in message news:xxxxx@ntdev…
> Rtl (at least in Win 8.1) has distinct AVL, RB and HashTable implementations.
>
> The advantage of binary trees is that they can automatically balance this cost - even if
they are slower versus optimal hashing
Another point to consider here is “who cares about the speed” one. Although reducing the number of times hat you have to access the tree/list/table/etc may be of paramount importance if every access to the data structure involves disk (or even rnetwork)access, for understandable reasons, it does
necessarily apply in situations when the target data structure is mainly located in memory. In such case increasing the size of the table in order to avoid collisions may actually slow the things down,instead ofspeeding them up,because of the increased probability of page faults that involve disk access…
Anton Bassov
+1
Yes that is why there are so many varieties of doing the same thing :-). Adaptive algorithms are there to switch mode I guess !
Pro
On Jun 11, 2015, at 1:28 AM, xxxxx@hotmail.com wrote:
> The advantage of binary trees is that they can automatically balance this cost - even if
> they are slower versus optimal hashingAnother point to consider here is “who cares about the speed” one. Although reducing the number of times hat you have to access the tree/list/table/etc may be of paramount importance if every access to the data structure involves disk (or even rnetwork)access, for understandable reasons, it does
necessarily apply in situations when the target data structure is mainly located in memory. In such case increasing the size of the table in order to avoid collisions may actually slow the things down,instead ofspeeding them up,because of the increased probability of page faults that involve disk access…Anton Bassov
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminarsTo unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer
Here are some links about cache effect(s)/page color -
http://yarchive.net/comp/linux/page_coloring.html
http://rolfed.com/nehalem/nehalemPaper.pdf
-Pro
Subject: Re: [ntdev] Hash Mapping at driver level
From: xxxxx@garlic.com
Date: Thu, 11 Jun 2015 10:02:37 -0700
To: xxxxx@lists.osr.com+1
Yes that is why there are so many varieties of doing the same thing :-). Adaptive algorithms are there to switch mode I guess !
Pro
On Jun 11, 2015, at 1:28 AM, xxxxx@hotmail.com wrote:
>> The advantage of binary trees is that they can automatically balance this cost - even if
>> they are slower versus optimal hashing
>
> Another point to consider here is “who cares about the speed” one. Although reducing the number of times hat you have to access the tree/list/table/etc may be of paramount importance if every access to the data structure involves disk (or even rnetwork)access, for understandable reasons, it does
> necessarily apply in situations when the target data structure is mainly located in memory. In such case increasing the size of the table in order to avoid collisions may actually slow the things down,instead ofspeeding them up,because of the increased probability of page faults that involve disk access…
>
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminarsTo unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer
> http://yarchive.net/comp/linux/page_coloring.html
BTW, once we are at it, in terms of potential performance improvement, N-way cache associativity happens to be pretty non-linear factor. Unfortunately, I cannot immediately find a link to a document that provides an in-depth analysis of cache associativity, but, IIRC, intoducing 2-way associativity gives a tremendous improvement over the direct 1-to-1 mapping, and intoducing 4-way associativity gives a similar improvement compared to 2-way one. However, 8-way associativity gives only a marginal (if any at all) improvement over 4-way one, and increasing N above 8 is clearly just a waste of transistors…
Anton Bassov
>going to be AT LEAST pointless on a UMA architecture where all the cores share the same memory
controller.
No.
Given the same number of transistors, shared cache will be much larger then per-core one.
–
Maxim S. Shatskih
Microsoft MVP on File System And Storage
xxxxx@storagecraft.com
http://www.storagecraft.com
> Given the same number of transistors, shared cache will be much larger then per-core one.
True, but in order to access this increased cache, a core has to deal with some external bus agent, which almost defies the very purpose of caching. OK, my statement about being “pointless” is, probably, indeed, a bit of exaggerration - after all, no matter how you look at it, accessing SRAM is, indeed, going to be much faster compared to DRAM access, even if this SRAM is external to the processor. Therefore, an external unified L3 cache may, indeed, speed the things up, because, no matter how you look at it, it is still going to be much faster compared to DRAM-based main memory, simply by the virtue of being implemented in SRAM …
Anton Bassov