I have been writing code in the kernel for about 1 year, and i am tired of typing the same code over and over to use Microsoft LIST_ENTRY.
I tried writing a template that I could then use for any class/structure I wanted in the kernel. It isn’t complete, but I would like to get the ideas/improvements from the experts here if anyone is interested.
I need to add 1 more template parameter to specify the member variable to be used for the listEntry, but for now I use m_listEntry in all my structures.
#ifndef LIST_H
#define LIST_H
#include <fltkernel.h>
#include <cttypes.h>
template
class ListEntry {
public:
ListEntry() {
// Initialize process linked list
InitializeListHead(&m_listHead);
KeInitializeSpinLock(&m_listLock);
}
~ListEntry() {
while (! IsEmpty()) {
T* obj = RemoveFront();
delete obj;
}
}
bool Append(T* _listEntry) {
KIRQL oldIrql;
KeAcquireSpinLock(&m_listLock, &oldIrql);
InsertTailList(&m_listHead, (_listEntry));
KeReleaseSpinLock(&m_listLock, oldIrql);
return true;
}
T First() {
KIRQL oldIrql;
KeAcquireSpinLock(&m_listLock, &oldIrql);
LIST_ENTRY* pEntry = m_listHead.Flink;
KeReleaseSpinLock(&m_listLock, oldIrql);
if (pEntry == &m_listHead) return NULL;
return CONTAINING_RECORD(pEntry, T, m_listEntry);
}
T* RemoveFront() {
KIRQL oldIrql;
KeAcquireSpinLock(&m_listLock, &oldIrql);
LIST_ENTRY* pEntry = RemoveHeadList( &m_listHead );
KeReleaseSpinLock(&m_listLock, oldIrql);
return CONTAINING_RECORD(pEntry, T, m_listEntry);
}
bool IsEmpty() {
return ! (FALSE == IsListEmpty(&m_listHead));
}
T* Delete(FindFn _fn) {
LIST_ENTRY* pEntry=NULL;
T* foundObj=NULL;
KIRQL oldIrql;
KeAcquireSpinLock(&m_listLock, &oldIrql);
pEntry = m_listHead.Flink;
while (pEntry != &m_listHead) {
T* pObj = CONTAINING_RECORD(pEntry, T, m_listEntry);
if (_fn(pObj)) {
RemoveEntryList(pEntry);
foundObj = pObj;
break;
}
pEntry = pEntry->Flink;
}
KeReleaseSpinLock(&m_listLock, oldIrql);
return foundObj;
}
T Find(FindFn _fn) {
LIST_ENTRY* pEntry=NULL;
T* foundObj=NULL;
KIRQL oldIrql;
KeAcquireSpinLock(&m_listLock, &oldIrql);
pEntry = m_listHead.Flink;
while (pEntry != &m_listHead) {
T* pObj = CONTAINING_RECORD(pEntry, T, m_listEntry);
if (_fn(*pObj)) {
foundObj = pObj;
break;
}
pEntry = pEntry->Flink;
}
KeReleaseSpinLock(&m_listLock, oldIrql);
return foundObj;
}
LIST_ENTRY m_listHead; //< List head
KSPIN_LOCK m_listLock; //< Spin lock
};
#endif</cttypes.h></fltkernel.h>
xxxxx@gmail.com wrote:
I have been writing code in the kernel for about 1 year, and i am tired of typing the same code over and over to use Microsoft LIST_ENTRY.
I tried writing a template that I could then use for any class/structure I wanted in the kernel. It isn’t complete, but I would like to get the ideas/improvements from the experts here if anyone is interested.
The idea is nice, but there are some conceptual issues here You don’t
need the spinlock in First – that’s pointless. It’s an atomic
operation. More importantly, however, is that locking in a list needs
to cover more than just these operations. Consider, for example, your
“Find” routine. You look for an entry, then return the found entry,
while leaving the entry on the list. However, as soon as you release
the lock, the item can be removed from the list by another thread. What
do you do then? Really, you almost need a “FindAndRemove” operation, so
that the entry is not part of the list when the lock is released.
In the end, because it gave the false “illusion” of safety, I removed
locking from my LIST_ENTRY wrapper template class and made it the
responsibility of the caller.
You also need to realize that you cannot use this file in any driver
that uses paged code, because the Microsoft compilers provide no way to
specify whether the generated code goes in a paged section or not.
I need to add 1 more template parameter to specify the member variable to be used for the listEntry, but for now I use m_listEntry in all my structures.
I took a similar approach.
–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.
Besides, you can just build a locked list on top of a list, and then
you can abstract ‘locked’ as well. Soon everything is a vast morass of
obscure abstractions …
No Paged Code be warned indeed.
Someday perhaps the compiler will get fixed?
Mark Roddy
On Mon, Jan 31, 2011 at 4:23 PM, Tim Roberts wrote:
> xxxxx@gmail.com wrote:
>> I have been writing code in the kernel for about 1 year, and i am tired of typing the same code over and over to use Microsoft LIST_ENTRY.
>> I tried writing a template that I could then use for any class/structure I wanted in the kernel. It isn’t complete, but I would like to get the ideas/improvements from the experts here if anyone is interested.
>
> The idea is nice, but there are some conceptual issues here ? You don’t
> need the spinlock in First – that’s pointless. ?It’s an atomic
> operation. ?More importantly, however, is that locking in a list needs
> to cover more than just these operations. ?Consider, for example, your
> “Find” routine. ?You look for an entry, then return the found entry,
> while leaving the entry on the list. ?However, as soon as you release
> the lock, the item can be removed from the list by another thread. ?What
> do you do then? ?Really, you almost need a “FindAndRemove” operation, so
> that the entry is not part of the list when the lock is released.
>
> In the end, because it gave the false “illusion” of safety, I removed
> locking from my LIST_ENTRY wrapper template class and made it the
> responsibility of the caller.
>
> You also need to realize that you cannot use this file in any driver
> that uses paged code, because the Microsoft compilers provide no way to
> specify whether the generated code goes in a paged section or not.
>
>> I need to add 1 more template parameter to specify the member variable to be used for the listEntry, but for now I use m_listEntry in all my structures.
>
> I took a similar approach.
>
> –
> Tim Roberts, xxxxx@probo.com
> Providenza & Boekelheide, Inc.
>
>
> —
> 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
>
"Consider, for example, your “Find” routine. You look for an entry, then return the found entry, while leaving the entry on the list. However, as soon as you release the lock, the item can be removed from the list by another thread. What do you do then? Really, you almost need a “FindAndRemove” operation, so that the entry is not part of the list when the lock is released. "
It seems to me there are two issues, 1) the integrity of the f/b links and thus the integrity of the list. 2) The integrity of the object.
I am only trying to achieve #1, so in your example the list was not modified by the find, the purpose of locking during the scan was just to ensure the list was not modified as I traversed it. Subsequent access and removal of the object from the list does not affect the thread that got access to it originally.
It seems you need the locks, just to preserve list integrity.
If I need to be concerned about the object lifetime i use refcounts on the objects, then I’d need to inc/decr the counts on add/remove. That could be a layer on top of this code or externalized to another set of functions.
xxxxx@gmail.com wrote:
It seems to me there are two issues, 1) the integrity of the f/b links and thus the integrity of the list. 2) The integrity of the object.
I am only trying to achieve #1, so in your example the list was not modified by the find, the purpose of locking during the scan was just to ensure the list was not modified as I traversed it. Subsequent access and removal of the object from the list does not affect the thread that got access to it originally.
It seems you need the locks, just to preserve list integrity.
That’s fine, as long as you define and document the parameters
carefully. Six months from now, when someone else tries to use your
routines, they will need to understand what protections are guaranteed
and what common operations are not. That’s what comments are for.
Really, it comes down to defining which operations are going to be used
most commonly, and providing ways to do those operations safely. As
another example, RemoveEntryList is a very nasty little cuss, because it
operates without the knowledge or involvement of the list head. Given
an item, it removes the item from whichever list it happens to be in.
You have to think carefully about how that might be used in your driver
in order to protect the list. You can make it a method of your class,
but there’s no particular guarantee (except through convention) that the
item being removed belongs to that list.
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.