list of FOs

NTFSD
1

Hi experts,

I need some advice here regarding FileObject storage.

In my FSFD, I want to maintain a list of all FOs a process opens and
closes(using CLEANUP).

I have made a datastructure of my own which has the process related info as
well as a linked list which contains teh pointers to the FOs

typedef struct _OPEN_FILE_INFO{

PFILE_OBJECT pFO;

struct _OPEN_FILE_INFO * pNextRecord;

}OPEN_FILE_INFO, *POPEN_FILE_INFO;

I add an entry to this list when I get a create request from the process, in
the IRP completion routine, if the request suceeds.

I delete an entry from this list when I get a CLEANUP request from the
process on an FO that is in this list.

My doubt is, this the correct way of handling this problem? AFAIK, there is
no way the OS will delete an FO before all processes that have open handles
will issue a cleanup.

–

  • amitr0
2

Use FltMgr contexts for this, they implement nearly the same feature.

Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com

----- Original Message -----
From: “amitr0”
To: “Windows File Systems Devs Interest List”
Sent: Thursday, May 11, 2006 11:07 AM
Subject: [ntfsd] list of FOs

Hi experts,

I need some advice here regarding FileObject storage.

In my FSFD, I want to maintain a list of all FOs a process opens and
closes(using CLEANUP).

I have made a datastructure of my own which has the process related info as
well as a linked list which contains teh pointers to the FOs

typedef struct _OPEN_FILE_INFO{

PFILE_OBJECT pFO;

struct _OPEN_FILE_INFO * pNextRecord;

}OPEN_FILE_INFO, *POPEN_FILE_INFO;

I add an entry to this list when I get a create request from the process, in
the IRP completion routine, if the request suceeds.

I delete an entry from this list when I get a CLEANUP request from the
process on an FO that is in this list.

My doubt is, this the correct way of handling this problem? AFAIK, there is
no way the OS will delete an FO before all processes that have open handles
will issue a cleanup.

–

- amitr0

—
Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17

You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com

3

No, the client specs are of a legacy driver, not Fltmgr :frowning:

On 5/11/06, Maxim S. Shatskih wrote:
>
> Use FltMgr contexts for this, they implement nearly the same feature.
>
> Maxim Shatskih, Windows DDK MVP
> StorageCraft Corporation
> xxxxx@storagecraft.com
> http://www.storagecraft.com
>
> ----- Original Message -----
> From: “amitr0”
> To: “Windows File Systems Devs Interest List”
> Sent: Thursday, May 11, 2006 11:07 AM
> Subject: [ntfsd] list of FOs
>
>
> Hi experts,
>
> I need some advice here regarding FileObject storage.
>
> In my FSFD, I want to maintain a list of all FOs a process opens and
> closes(using CLEANUP).
>
> I have made a datastructure of my own which has the process related info
> as
> well as a linked list which contains teh pointers to the FOs
>
>
> typedef struct _OPEN_FILE_INFO{
>
> PFILE_OBJECT pFO;
>
> struct _OPEN_FILE_INFO * pNextRecord;
>
> }OPEN_FILE_INFO, *POPEN_FILE_INFO;
>
>
>
> I add an entry to this list when I get a create request from the process,
> in
> the IRP completion routine, if the request suceeds.
>
> I delete an entry from this list when I get a CLEANUP request from the
> process on an FO that is in this list.
>
>
>
> My doubt is, this the correct way of handling this problem? AFAIK, there
> is
> no way the OS will delete an FO before all processes that have open
> handles
> will issue a cleanup.
>
>
> –
>
> - amitr0
>
> —
> Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17
>
> You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
> —
> Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17
>
> You are currently subscribed to ntfsd as: xxxxx@gmail.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>

–

- amitr0

4

Then use some container (similar to STL map, for instance, hash table or
AVL tree indexed by FCB pointer) which will hold the (FCB pointer -> your
context) records.

You allocate the record in pre-MJ_CREATE path (before IoCallDriver down),
and insert it to the table in post-MJ_CREATE path.

The FCB pointer is at FileObject->FsContext, valid starting from the post
create path.

Do not forget to refcount the record if the file with the same FCB will be
opened several times. In pre-MJ_CLOSE, deref it, destroy it if derefed to zero.

Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com

----- Original Message -----
From: “amitr0”
To: “Windows File Systems Devs Interest List”
Sent: Thursday, May 11, 2006 1:37 PM
Subject: Re: [ntfsd] list of FOs

No, the client specs are of a legacy driver, not Fltmgr :frowning:

On 5/11/06, Maxim S. Shatskih wrote:
>
> Use FltMgr contexts for this, they implement nearly the same feature.
>
> Maxim Shatskih, Windows DDK MVP
> StorageCraft Corporation
> xxxxx@storagecraft.com
> http://www.storagecraft.com
>
> ----- Original Message -----
> From: “amitr0”
> To: “Windows File Systems Devs Interest List”
> Sent: Thursday, May 11, 2006 11:07 AM
> Subject: [ntfsd] list of FOs
>
>
> Hi experts,
>
> I need some advice here regarding FileObject storage.
>
> In my FSFD, I want to maintain a list of all FOs a process opens and
> closes(using CLEANUP).
>
> I have made a datastructure of my own which has the process related info
> as
> well as a linked list which contains teh pointers to the FOs
>
>
> typedef struct _OPEN_FILE_INFO{
>
> PFILE_OBJECT pFO;
>
> struct _OPEN_FILE_INFO * pNextRecord;
>
> }OPEN_FILE_INFO, *POPEN_FILE_INFO;
>
>
>
> I add an entry to this list when I get a create request from the process,
> in
> the IRP completion routine, if the request suceeds.
>
> I delete an entry from this list when I get a CLEANUP request from the
> process on an FO that is in this list.
>
>
>
> My doubt is, this the correct way of handling this problem? AFAIK, there
> is
> no way the OS will delete an FO before all processes that have open
> handles
> will issue a cleanup.
>
>
> –
>
> - amitr0
>
> —
> Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17
>
> You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
> —
> Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17
>
> You are currently subscribed to ntfsd as: xxxxx@gmail.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>

–

- amitr0

—
Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17

You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com

5

Thanks maxim.

6

Maxim (and ofcourse others),

I am facing a problem in storing the pointers to in the list of FOs I am
maintainnig.

I find manytimes that the pointers to the FOS in the list are spurious. (the
method I am using to figure out whether teh pFO is valid is by checking hte
size parameter pFileObject->Size, which should be 112).

The method I use to add and delete pFOs to my linked list is:

when a creat is isued, i let is pass down and in the comlpetion routine I
take the pointer to the FO and put it to my list.

During cleanup, I remove the pFO node from the list before letting the IRP
actually delete the pFO.

All these operations of adding to a list and removing is done inside a
spinlock protected section, so the multithreading issues are over ruled.

Can someone tell me why this is happening…
also is there any otehr method to verify whether the pFileObject is a valid
one of not, apart from the hard coded size value, which is ugly.

7

What makes Sachin India’s highest paid sports celebrity?, Share your knowledge on Yahoo! India Answers
Send instant messages to your online friends - NOW

8

If I need to store a linked list of some data which is accessible,
traversable and modifyable across all the threads of the various dispatch
routines, which essentially means that the lists would be called, traversed
deleted and nodes added many times in very short time intervals, is a spin
lock a good way to implement locking across different threads?

I find that I get DRIVER_IRQL_LESS_THAN_EQUAL_TO and it crashes, though I
have been careful to use nonpaged pool everywhere. Also, the traversal
mechanism is my own implementation, not the standard Kernel List data
structures.

Please advice.

Should I use some thing else instead, like Fast Mutexes?

9

A spinlock is very rarely the correct synchronization mechanism in a filesystem driver. Use fast mutices if all accesses to the list are read/write. The more likely situation is that for many accesses, you’ll only be reading the list, in which case you should use an ERESOURCE, and acquire it shared for read-only list access.

It sounds like your crash is just a bug in your list handling, probably following a bad pointer. Debug it.

  • Dan.
    ----- Original Message -----
    From: amitr0
    To: Windows File Systems Devs Interest List
    Sent: Wednesday, May 17, 2006 10:14 AM
    Subject: Re: [ntfsd] list of FOs

If I need to store a linked list of some data which is accessible, traversable and modifyable across all the threads of the various dispatch routines, which essentially means that the lists would be called, traversed deleted and nodes added many times in very short time intervals, is a spin lock a good way to implement locking across different threads?

I find that I get DRIVER_IRQL_LESS_THAN_EQUAL_TO and it crashes, though I have been careful to use nonpaged pool everywhere. Also, the traversal mechanism is my own implementation, not the standard Kernel List data structures.

Please advice.

Should I use some thing else instead, like Fast Mutexes?

— Questions? First check the IFS FAQ at https://www.osronline.com/article.cfm?id=17 You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a blank email to xxxxx@lists.osr.com

10

Dan,

"A spinlock is very rarely the correct synchronization mechanism in a
filesystem driver. "

Why is that so? Is it because becasue spin locks rasise the IRQL to dispatch
level?

Can we use fast mutexes for multiprocessor systems safely? Reading Nagar’s
book I have some doubts in this issue.

Regards,

Amitrajit

11

>Why is that so? Is it because becasue spin locks rasise the IRQL to dispatch level?

That, plus:
-spinlocks lack reader/writer semantics
-spinlocks are unnecessary because most filesytem/filter work can be done at passive level
-filesystems sometimes need to hold locks much longer than is wise with a spinlock
-multiprocessor spin lock contention is nasty stuff-better to have a bunch of threads in a wait state than a busy wait

Can we use fast mutexes for multiprocessor systems safely?

Certainly. Both fast mutices and ERESOURCES are completely compatible with muliprocessor systems.

BTW, is this list a list of all the open file objects on the system? If so, I would suggest that a linked list is the wrong approach (use a hash table). Your performance will suffer greatly doing a O(n) linked list search on every I/O.

  • Dan.
    ----- Original Message -----
    From: amitr0
    To: Windows File Systems Devs Interest List
    Sent: Thursday, May 18, 2006 2:52 AM
    Subject: Re: [ntfsd] list of FOs

Dan,

"A spinlock is very rarely the correct synchronization mechanism in a filesystem driver. "

Why is that so? Is it because becasue spin locks rasise the IRQL to dispatch level?

Can we use fast mutexes for multiprocessor systems safely? Reading Nagar’s book I have some doubts in this issue.

Regards,

Amitrajit
— Questions? First check the IFS FAQ at https://www.osronline.com/article.cfm?id=17 You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a blank email to xxxxx@lists.osr.com

12

Dan,

Thanks for the wonderful explanation. It helps.

"BTW, is this list a list of all the open file objects on the system? If
so, I would suggest that a linked list is the wrong approach (use a hash
table). Your performance will suffer greatly doing a O(n) linked list
search on every I/O. "

Yes, it is, and I am planning to implement the hashing mechanism, I believe
one such already exists in the filespy code fro reference. Just that this
was a prototype and was being used a a proof of concept. Though I do
absolutely agree that, even for a prototype it IS BAD design.

one more thing, though this is offtopic in this thread, still:

in Windwos NT/2K/XP, how is multiprocessing implemented, the minimum
schedulable entity being a thread here, on a ,ultiprocessor machine, does NT
schedule all threads of a process on a single processor, or can a single
process also span over different processors while execution?

Sorry if it is a stupid question, but better learn late than learn never.

amitr0

13

Multiple threads from the same process can be scheduled on different processors.
----- Original Message -----
From: amitr0
To: Windows File Systems Devs Interest List
Sent: Thursday, May 18, 2006 6:41 AM
Subject: Re: [ntfsd] list of FOs

Dan,

Thanks for the wonderful explanation. It helps.

"BTW, is this list a list of all the open file objects on the system? If so, I would suggest that a linked list is the wrong approach (use a hash table). Your performance will suffer greatly doing a O(n) linked list search on every I/O. "

Yes, it is, and I am planning to implement the hashing mechanism, I believe one such already exists in the filespy code fro reference. Just that this was a prototype and was being used a a proof of concept. Though I do absolutely agree that, even for a prototype it IS BAD design.

one more thing, though this is offtopic in this thread, still:

in Windwos NT/2K/XP, how is multiprocessing implemented, the minimum schedulable entity being a thread here, on a ,ultiprocessor machine, does NT schedule all threads of a process on a single processor, or can a single process also span over different processors while execution?

Sorry if it is a stupid question, but better learn late than learn never.

amitr0
— Questions? First check the IFS FAQ at https://www.osronline.com/article.cfm?id=17 You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a blank email to xxxxx@lists.osr.com

14

aah, thanks yet again.

But tell me, in the hashing approach even, there would be collisions, and I
need to maintain a linked list for each hash bucket, so I cannot avoif O(n)
all the way, can I?

On 5/18/06, Dan Kyler wrote:
>
> Multiple threads from the same process can be scheduled on different
> processors.
>
> ----- Original Message -----
> From: amitr0
> To: Windows File Systems Devs Interest List
> Sent: Thursday, May 18, 2006 6:41 AM
> Subject: Re: [ntfsd] list of FOs
>
>
> Dan,
>
> Thanks for the wonderful explanation. It helps.
>
> "BTW, is this list a list of all the open file objects on the system? If
> so, I would suggest that a linked list is the wrong approach (use a hash
> table). Your performance will suffer greatly doing a O(n) linked list
> search on every I/O. "
>
> Yes, it is, and I am planning to implement the hashing mechanism, I
> believe one such already exists in the filespy code fro reference. Just that
> this was a prototype and was being used a a proof of concept. Though I do
> absolutely agree that, even for a prototype it IS BAD design.
>
> one more thing, though this is offtopic in this thread, still:
>
> in Windwos NT/2K/XP, how is multiprocessing implemented, the minimum
> schedulable entity being a thread here, on a ,ultiprocessor machine, does NT
> schedule all threads of a process on a single processor, or can a single
> process also span over different processors while execution?
>
> Sorry if it is a stupid question, but better learn late than learn never.
>
> amitr0
> — Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17 You are currently subscribed
> to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a blank
> email to xxxxx@lists.osr.com
>
>
> —
> Questions? First check the IFS FAQ at
> https://www.osronline.com/article.cfm?id=17
>
> You are currently subscribed to ntfsd as: unknown lmsubst tag argument: ‘’
>
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>

–

- amitr0

15

>

in Windwos NT/2K/XP, how is multiprocessing implemented, the minimum
schedulable entity being a thread here, on a ,ultiprocessor machine,
does NT schedule all threads of a process on a single processor, or
can a single process also span over different processors while execution?

A single process can span multiple processors. For example, look at the
last parameter of the win32 api CreateIoCompletionPort. It states, “If
this parameter is zero, the system allows as many concurrently running
threads as there are processors in the system.”. This function has this
param for a reason…

Sorry if it is a stupid question, but better learn late than learn never.

So true, better late than never

amitr0
— Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17 You are currently
subscribed to ntfsd as: unknown lmsubst tag argument: ‘’ To
unsubscribe send a blank email to xxxxx@lists.osr.com

16

thanks matty…

now going a step further into this…

the sync mechanisms are for locking and protecting critical sections b/w
processors.

thus, if there is a lock L and one thread takes this lock then the code in
the kernel implementing this lock should be doing something like

MOV BYTE PTR [address], value

wher address is the addrs of the lock variable and the value is the state of
the lock. Now what I am unable to understand (maybe becuse I am too stupid,
and my basics are wrong) is that *is it the OS who implements the safety of
this memory location* or the hardware. What would stop two threads from
playing with the value at this address?

17

First the locking mechanisms are to protect against multiple paths of
execution. A path can be a thread, but it can also be hardware or software
interrupt (such as a DPC routine). You need to protect against all of
these, since even with a single processor a second thread can be scheduled
and impact an update of a critical structure.

For multiprocessor machines all the lock mechanisms are built around
multi-processor safe instructions. A common example is the DDK’s
InterlockExchange call which swaps a value in memory with a specified value.
At its simplest level, a spinlock uses this call to get the old lock value
and set a new one, if the old value indicated no one held the lock it the
caller is now the owner of the lock. More complex mechanisms such as
RESOURCES are built up from the basics.

If you are asking this level of question seriously consider taking a DDK
course. Since you are dealing with file systems, I would recomend the OSR
class since that will prepare you well for their file system course.

–
Don Burn (MVP, Windows DDK)
Windows 2k/XP/2k3 Filesystem and Driver Consulting
Remove StopSpam from the email to reply

“amitr0” wrote in message news:xxxxx@ntfsd…
thanks matty…

now going a step further into this…

the sync mechanisms are for locking and protecting critical sections b/w
processors.

thus, if there is a lock L and one thread takes this lock then the code in
the kernel implementing this lock should be doing something like

MOV BYTE PTR [address], value

wher address is the addrs of the lock variable and the value is the state of
the lock. Now what I am unable to understand (maybe becuse I am too stupid,
and my basics are wrong) is that is it the OS who implements the safety of
this memory location or the hardware. What would stop two threads from
playing with the value at this address?

18

It is the kernel that protects the memory. Stop what your doing and go
here -> http://channel9.msdn.com/Shows/Going_Deep

One of these videos by Dave Probart explains this so well. (if I
remember correctly it’s one of the dave p video’s).

The three videos in this series combined are about 2 hours, but it is so
worth watching. I really need to watch these video’s again!!!

This guy will explain the locking types in the video, describe them, and
illistrate them on the black board…

You will gain a lot by watching this
guy!!!

m

P.S. your question about the race condition is explained well in these
videos

amitr0 wrote:

thanks matty…

now going a step further into this…

the sync mechanisms are for locking and protecting critical sections
b/w processors.

thus, if there is a lock L and one thread takes this lock then the
code in the kernel implementing this lock should be doing something like

MOV BYTE PTR [address], value

wher address is the addrs of the lock variable and the value is the
state of the lock. Now what I am unable to understand (maybe becuse I
am too stupid, and my basics are wrong) is that *is it the OS who
implements the safety of this memory location * or the hardware. What
would stop two threads from playing with the value at this address?
— Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17 You are currently
subscribed to ntfsd as: unknown lmsubst tag argument: ‘’ To
unsubscribe send a blank email to xxxxx@lists.osr.com

19

Don

First of all thanks for the reply, it ws educative.

“If you are asking this level of question seriously consider taking a DDK
course. Since you are dealing with file systems, I would recomend the OSR
class since that will prepare you well for their file system course.”

Well, honestly, I am from a poor developing country, where asking the
employer to sponser a 3000 dollar course is consider sin enough to get you
fired, and brand you as incompetent. So no scope there, all the best I can
do, is read rad and read more, si and debug the windows code to get insight,
and when I am confused, ask you elite people, and hope to get an answer, and
sometimes a rebuke, but I never mind them, as they are always for my
betterment.

Thanks again,

amitr0

20

The simplest implementation is using a hash table with linked lists in
each hash bucket. My general rule of thumb is that I don’t want more
than around 10 entries in any hash bucket for acceptable performance.
If I’m getting more entries than that, either the table is too small
(lots of hash buckets are over the threshold) or the hash algorithm is
bad (a few hash buckets are over the threshold). To solve this issue
you can increase the size of the hash table, change your hash function
or move to trees in the individual hash buckets (e.g., splay trees,
which work fairly well in a situation like this.)

We published an article with sample code for a fixed size (256 entry in
the sample code) hash table that employs linked lists in the hash
buckets recently (http://www.osronline.com/article.cfm?article=443) and
the motivation was use in a file system. The table uses ERESOURCE
objects (one to cover the entire table in case someone needs to walk the
entire table and make changes to it, and then one per hash table
bucket.) The sample code doesn’t protect against duplicates (which is a
lot more complex to make efficient and correct) but if that’s a
requirement, I can explain it further.

Regards,

Tony

Tony Mason

Consulting Partner

OSR Open Systems Resources, Inc.

http://www.osr.com

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of amitr0
Sent: Thursday, May 18, 2006 8:58 AM
To: ntfsd redirect
Subject: Re: [ntfsd] list of FOs

aah, thanks yet again.

But tell me, in the hashing approach even, there would be collisions,
and I need to maintain a linked list for each hash bucket, so I cannot
avoif O(n) all the way, can I?

On 5/18/06, Dan Kyler wrote:

Multiple threads from the same process can be scheduled on different
processors.

----- Original Message -----

From: amitr0 mailto:xxxxx

To: Windows File Systems Devs Interest List mailto:xxxxx

Sent: Thursday, May 18, 2006 6:41 AM

Subject: Re: [ntfsd] list of FOs

Dan,

Thanks for the wonderful explanation. It helps.

"BTW, is this list a list of all the open file objects on the system?
If so, I would suggest that a linked list is the wrong approach (use a
hash table). Your performance will suffer greatly doing a O(n) linked
list search on every I/O. "

Yes, it is, and I am planning to implement the hashing mechanism, I
believe one such already exists in the filespy code fro reference. Just
that this was a prototype and was being used a a proof of concept.
Though I do absolutely agree that, even for a prototype it IS BAD
design.

one more thing, though this is offtopic in this thread, still:

in Windwos NT/2K/XP, how is multiprocessing implemented, the minimum
schedulable entity being a thread here, on a ,ultiprocessor machine,
does NT schedule all threads of a process on a single processor, or can
a single process also span over different processors while execution?

Sorry if it is a stupid question, but better learn late than learn
never.

amitr0

— Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17 You are currently subscribed
to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a
blank email to xxxxx@lists.osr.com

—
Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17

You are currently subscribed to ntfsd as: unknown lmsubst tag argument:
‘’

To unsubscribe send a blank email to xxxxx@lists.osr.com

–

- amitr0 — Questions? First check the IFS FAQ at
https://www.osronline.com/article.cfm?id=17 You are currently subscribed
to ntfsd as: unknown lmsubst tag argument: ‘’ To unsubscribe send a
blank email to xxxxx@lists.osr.com</mailto:xxxxx></mailto:xxxxx>