Optimized LIST

Musharraf_Hussain · June 15, 2011, 7:55am

Hi all,

I am writing minifilter driver working to intercept file for IRP_MJ_CREATE, and I using LIST_ENTRY.

When my list contains 1000 files to compare during intercept IRP_MJ_CREATE, system performance is being little bit slow.

If anybody knows fast technique technique or any possilbities to use DATABASE in driver.

thanks

Mark_S_Edwards · June 15, 2011, 8:02am

Have you tried Generic Tables ?

Read the WDK documentation for RtlInitialiseGenericTable to see if
they would work for you.

Mark.

At 12:59 15/06/2011, xxxxx@yahoo.com wrote:

Hi all,

I am writing minifilter driver working to intercept file for
IRP_MJ_CREATE, and I using LIST_ENTRY.

When my list contains 1000 files to compare during intercept
IRP_MJ_CREATE, system performance is being little bit slow.

If anybody knows fast technique technique or any possilbities to use
DATABASE in driver.

thanks

Alex_Carp · June 15, 2011, 12:57pm

In addition to what Mark said, maybe you will find the article “Kernel Mode
Basics: Splay Trees” (http://www.osronline.com/article.cfm?article=516)
helpful.

Make sure that you don’t use an exclusive lock for the tree or table since
that can have a significant performance impact when there are a lot of
concurrent IPR_MJ_CREATE requests. I would use an ERESOURCE (since you’re in
the CREATE path, so at PASSIVE_LEVEL) but make sure that you never cause
splaying when you have the resource acquired shared. I’ve used an AVL table
(see RtlInitializeGenericTableAvl, coverd in the MSDN documentation for
RtlInitializeGenericTable
(http://msdn.microsoft.com/en-us/library/ff552989(v=vs.85).aspx)) which
doesn’t change on reading the tree (which was important since there is no
api for RtlLookupElementGenericTable without splaying).

Thanks,
Alex.

Musharraf_Hussain · June 17, 2011, 6:56am

Hi Mark,

I implemented Generic table as following :

//structure that mainting into Table

typedef struct _FL_TABLE
{
BYTE m_bytStatus;
BYTE m_bytType;
BYTE m_bytDel;
PVOID m_DataPath;

}FLTABLE, *PFLTABLE;

//Inserting into table as following

FLTABLE tbObj;
BOOLEAN ret;

tbObj.m_DataPath = (PVOID)r_strDataPath.Buffer; / r_strDataPath is UNICODE_STRING filled with
/ RtlInitUnicodeString

RtlInsertElementGenericTable(&gLockTable,&tbObj,sizeof(FLTABLE), &ret);

// Comparing element as following :

BOOLEAN bSuccess = FALSE;

FLTABLE tbObj;
BOOLEAN ret;
tbObj.m_DataPath = (PVOID)uPath.Buffer; //uPath is UNICODE_STRING data type is allocated buffer

if(RtlLookupElementGenericTable(&gLockTable,&tbObj) != NULL)
bSuccess = TRUE;

// Compare function

RTL_GENERIC_COMPARE_RESULTS CompareElement ( struct _RTL_GENERIC_TABLE *Table, PVOID FirstStruct, PVOID SecondStruct )
{

if(((FLTABLE*)FirstStruct)->m_DataPath == ((FLTABLE*)SecondStruct)->m_DataPath)
return GenericEqual;

if(((FLTABLE*)FirstStruct)->m_DataPath < ((FLTABLE*)SecondStruct)->m_DataPath)
return GenericLessThan;

return GenericGreaterThan;
}

//Allocate
PVOID AllocElement ( struct _RTL_GENERIC_TABLE *Table, CLONG ByteSize )
{
return ExAllocatePoolWithTag(PagedPool,ByteSize,‘gtb1’);
}

VOID FreeElement ( struct _RTL_GENERIC_TABLE *Table, PVOID Buffer )
{
ExFreePoolWithTag(Buffer,‘gtb1’);
return;
}

Note : Problem is that not comparing successfully.

Thanks

Musharraf_Hussain · June 20, 2011, 1:00am

Hi all,

I think problem in my Compare routine

Let me know if anybody can help me.

Thanks

mm1 · June 20, 2011, 6:14am

I don’t know much about fsf’s, but your compare routine is comparing
pointers. Is that what you want, or do you want to compare the values they
point to?

Mm
On Jun 17, 2011 6:56 AM, wrote:
> Hi Mark,
>
> I implemented Generic table as following :
>
>
> //structure that mainting into Table
>
> typedef struct _FL_TABLE
> {
> BYTE m_bytStatus;
> BYTE m_bytType;
> BYTE m_bytDel;
> PVOID m_DataPath;
>
> }FLTABLE, PFLTABLE;
>
>
> //Inserting into table as following
>
> FLTABLE tbObj;
> BOOLEAN ret;
>
> tbObj.m_DataPath = (PVOID)r_strDataPath.Buffer; / r_strDataPath is
UNICODE_STRING filled with
> / RtlInitUnicodeString
>
>
> RtlInsertElementGenericTable(&gLockTable,&tbObj,sizeof(FLTABLE), &ret);
>
>
>
> // Comparing element as following :
>
> BOOLEAN bSuccess = FALSE;
>
> FLTABLE tbObj;
> BOOLEAN ret;
> tbObj.m_DataPath = (PVOID)uPath.Buffer; //uPath is UNICODE_STRING data
type is allocated buffer
>
> if(RtlLookupElementGenericTable(&gLockTable,&tbObj) != NULL)
> bSuccess = TRUE;
>
>
>
> // Compare function
>
> RTL_GENERIC_COMPARE_RESULTS CompareElement ( struct _RTL_GENERIC_TABLE
Table, PVOID FirstStruct, PVOID SecondStruct )
> {
>
> if(((FLTABLE)FirstStruct)->m_DataPath ==
((FLTABLE)SecondStruct)->m_DataPath)
> return GenericEqual;
>
> if(((FLTABLE*)FirstStruct)->m_DataPath <
((FLTABLE*)SecondStruct)->m_DataPath)
> return GenericLessThan;
>
> return GenericGreaterThan;
> }
>
> //Allocate
> PVOID AllocElement ( struct _RTL_GENERIC_TABLE *Table, CLONG ByteSize )
> {
> return ExAllocatePoolWithTag(PagedPool,ByteSize,‘gtb1’);
> }
>
>
> VOID FreeElement ( struct _RTL_GENERIC_TABLE *Table, PVOID Buffer )
> {
> ExFreePoolWithTag(Buffer,‘gtb1’);
> return;
> }
>
> Note : Problem is that not comparing successfully.
>
> Thanks
>
>
> —
> NTFSD is sponsored by OSR
>
> For our schedule of debugging and file system 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

Ayush_Gupta-2 · June 20, 2011, 3:18pm

I am not sure if this will ever work.
Here is why (or maybe I did not look at it properly at all?):

You have kept a copy of the Unicode string buffer pointer that was
initialized using RtlInitUnicodeString- which effectively means that it is
pointing to somewhere on the stack and is bound to change after the function
finishes. You are storing the file table structure in generic table with a
pointer to string which has almost 0 chance of remaining valid.
This is not C++ that you just overload the ==, <, > operator and they
will do the string comparison for you. Try string comparison functions.
Oh and btw, in extension to point 1, I hope that you do know that
UNICODE_STRINGS are NOT NULL terminated. So, you know what will happen if
you just store that buffer without a trailing NULL and don’t have length of
that buffer?

Regards,
Ayush Gupta
Software Consultant & Owner,
AI Consulting

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of
xxxxx@yahoo.com
Sent: Friday, June 17, 2011 4:29 PM
To: Windows File Systems Devs Interest List
Subject: RE:[ntfsd] Optimized LIST

Hi Mark,

I implemented Generic table as following :

//structure that mainting into Table

typedef struct _FL_TABLE
{
BYTE m_bytStatus;
BYTE m_bytType;
BYTE m_bytDel;
PVOID m_DataPath;

}FLTABLE, *PFLTABLE;

//Inserting into table as following

FLTABLE tbObj;
BOOLEAN ret;

tbObj.m_DataPath = (PVOID)r_strDataPath.Buffer; / r_strDataPath is
UNICODE_STRING filled with
/
RtlInitUnicodeString

RtlInsertElementGenericTable(&gLockTable,&tbObj,sizeof(FLTABLE), &ret);

// Comparing element as following :

BOOLEAN bSuccess = FALSE;

FLTABLE tbObj;
BOOLEAN ret;
tbObj.m_DataPath = (PVOID)uPath.Buffer; //uPath is UNICODE_STRING data type
is allocated buffer

if(RtlLookupElementGenericTable(&gLockTable,&tbObj) != NULL)
bSuccess = TRUE;

// Compare function

RTL_GENERIC_COMPARE_RESULTS CompareElement ( struct _RTL_GENERIC_TABLE
*Table, PVOID FirstStruct, PVOID SecondStruct ) {

if(((FLTABLE*)FirstStruct)->m_DataPath ==
((FLTABLE*)SecondStruct)->m_DataPath)
return GenericEqual;

if(((FLTABLE*)FirstStruct)->m_DataPath <
((FLTABLE*)SecondStruct)->m_DataPath)
return GenericLessThan;

return GenericGreaterThan;
}

//Allocate
PVOID AllocElement ( struct _RTL_GENERIC_TABLE *Table, CLONG ByteSize ) {
return ExAllocatePoolWithTag(PagedPool,ByteSize,‘gtb1’);
}

VOID FreeElement ( struct _RTL_GENERIC_TABLE *Table, PVOID Buffer ) {
ExFreePoolWithTag(Buffer,‘gtb1’);
return;
}

Note : Problem is that not comparing successfully.

Thanks

NTFSD is sponsored by OSR

For our schedule of debugging and file system 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

Musharraf_Hussain · June 21, 2011, 2:16am

Hi all,

I implemented successfully, but anybody know about maximum entry limit in Generic Table or limit of memory ?

Let me know if anybody knows that.

Thanks

OSR_Community_User · June 22, 2011, 2:08pm

> I implemented successfully, but anybody know about maximum entry limit in Generic Table or limit of memory ?

The limit is only memory, and on pre-Vista nonpaged pool is IIRC limited by 256MB, with this number being possibly different across different Windows SKUs.

On Vista+ the limit is much larger.

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

Musharraf_Hussain · June 27, 2011, 4:30am

Hi all,

I getting problem during deleting element from the Generic Table, I have more than 10 elements in table, but exception raised in first element deletion, however sometimes it deletes 2-3 elments.

Insertion code :

FLDATA tbObj;
BOOLEAN ret;

GetLockMutex();

RtlStringCbCopyW(tbObj.m_DataPath,r_strDataPath.MaximumLength,r_strDataPath.Buffer);
RtlStringCbCopyW(tbObj.m_User,r_strUser.MaximumLength,r_strUser.Buffer);

RtlInsertElementGenericTable(&gLockTable,&tbObj,sizeof(FLDATA), &ret);

ReleaseLockMutex();

// Deleting element code :

PFLDATA pRestartKey = NULL;
PFLDATA pDataElement = NULL;
GetLockMutex();
for (pDataElement = RtlEnumerateGenericTableWithoutSplaying ( &gLockTable, &pRestartKey );
pDataElement != NULL;
pDataElement = RtlEnumerateGenericTableWithoutSplaying ( &gLockTable, &pRestartKey ))
{
#ifdef _DEBUG
DbgPrint(“Removed Element : %ws\n”, pDataElement->m_DataPath);
#endif
RtlDeleteElementGenericTable(&gLockTable,pDataElement);
}
ReleaseLockMutex();

// Compare, Allocation and Free function

RTL_GENERIC_COMPARE_RESULTS CompareLockElement (PRTL_GENERIC_TABLE Table, PVOID FirstStruct, PVOID SecondStruct )
{
UNICODE_STRING uPath, uStr;
PAGED_CODE();

RtlInitUnicodeString(&uPath,((FLDATA*)FirstStruct)->m_DataPath);
RtlInitUnicodeString(&uStr,((FLDATA*)SecondStruct)->m_DataPath);

if(RtlCompareUnicodeString(&uStr,&uPath,TRUE)== 0 )
return GenericEqual;

if(RtlCompareUnicodeString(&uStr,&uPath,TRUE)< 0)
return GenericLessThan;

return GenericGreaterThan;
}
PVOID AllocLockElement ( PRTL_GENERIC_TABLE Table, CLONG ByteSize )
{
PAGED_CODE();
return ExAllocatePoolWithTag(PagedPool,ByteSize,‘gtb1’);
}

VOID FreeLockElement ( PRTL_GENERIC_TABLE Table, PVOID Buffer )
{
PAGED_CODE();
ExFreePoolWithTag(Buffer,‘gtb1’);
return;
}

Let me know if anybody knows the problem.

Thanks