{"id":11963,"date":"2010-12-20T07:00:01","date_gmt":"2010-12-20T07:00:01","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2010\/12\/20\/developing-the-method-for-taking-advantage-of-the-fact-that-the-overlapped-associated-with-asynchronous-io-is-passed-by-address\/"},"modified":"2010-12-20T07:00:01","modified_gmt":"2010-12-20T07:00:01","slug":"developing-the-method-for-taking-advantage-of-the-fact-that-the-overlapped-associated-with-asynchronous-io-is-passed-by-address","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20101220-01\/?p=11963","title":{"rendered":"Developing the method for taking advantage of the fact that the OVERLAPPED associated with asynchronous I\/O is passed by address"},"content":{"rendered":"

\n\nYou can take advantage of the fact that the\nOVERLAPPED<\/code> associated with asynchronous I\/O is\npassed by address<\/a>,\nbut there was some confusion about how this technique could\n“work” when kernel mode has no idea that you are playing this trick.\n<\/p>\n

\nWhether kernel mode is in on the trick is immaterial since it is not\npart of the trick.\n<\/p>\n

\nLet’s start with a version of the code which does not take advantage\nof the OVERLAPPED<\/code> structure address in the way\ndescribed in the article.\nThis is a technique I found in a book on advanced Windows programming:\n<\/p>\n

\n#define MAX_OVERLAPPED 10 \/\/ let's do 10 I\/O's at a time\n\/\/ data to associate with each OVERLAPPED\nstruct OTHERDATA { ... };\nOVERLAPPED MasterOverlapped[MAX_OVERLAPPED];\nOTHERDATA OtherData[MAX_OVERLAPPED];\nOTHERDATA* FindOtherDataFromOverlapped(OVERLAPPED *lpOverlapped)\n{\n ptrdiff_t index = lpOverlapped - MasterOverlapped;\n return &OtherData[index];\n}\n\/\/ I\/O is issued via\n\/\/ ReadFileEx(hFile, lpBuffer, nNumberOfBytesToRead,\n\/\/            &MasterOverlapped[i], CompletionRoutine);\nvoid CALLBACK CompletionRoutine(\n    DWORD dwErrorCode,\n    DWORD dwNumberOfBytesTransferred,\n    LPOVERLAPPED lpOverlapped)\n{\n OTHERDATA *lpOtherData =\n                       FindOtherDataFromOverlapped(lpOverlapped);\n ... do stuff with lpOverlapped and lpOtherData ...\n}\n<\/pre>\n
\nThis version of the code uses the address of the\nOVERLAPPED<\/code> structure to determine the\nlocation in the MasterOverlapped<\/code> table\nand uses the corresponding entry in the parallel array\nat OtherData<\/code> to hold the other data.\n<\/p>\n
\nLet’s make this code worse before we make it better:\n<\/p>\n
\nOTHERDATA* FindOtherDataFromOverlapped(OVERLAPPED *lpOverlapped)\n{\n for (int index = 0; index < MAX_OVERLAPPED; index++) {\n  if (&MasterOverlapped[index] == lpOverlapped) {\n   return &OtherData[index];\n  }\n }\n FatalError(); \/\/ should never be reached\n}\n<\/pre>\n
\nInstead of doing simple pointer arithmetic to recover\nthe index, we walk the array testing the pointers.\nThis is naturally worse than doing pointer arithmetic, but\nwatch what this step allows us to do:\nFirst, we reorganize the data so that instead of two\nparallel arrays, we have a single array of a compound\nstructure.\n<\/p>\n
\nstruct OVERLAPPEDEX\n{\n OVERLAPPED Overlapped;\n OTHERDATA OtherData;\n};\nOVERLAPPEDEX Master[MAX_OVERLAPPED];\nOTHERDATA* FindOtherDataFromOverlapped(OVERLAPPED *lpOverlapped)\n{\n for (int index = 0; index < MAX_OVERLAPPED; index++) {\n  if (&Master[index].Overlapped == lpOverlapped) {\n   return &Master[index].OtherData;\n  }\n }\n FatalError(); \/\/ should never be reached\n}\n\/\/ I\/O is issued via\n\/\/ ReadFileEx(hFile, lpBuffer, nNumberOfBytesToRead,\n\/\/            &Master[i].Overlapped, CompletionRoutine);\n<\/pre>\n
\nAll we did was consolidate the parallel arrays into a single array.\n<\/p>\n
\nNow that it’s an array of compound structures, we don’t need\nto carry two pointers around (one to the OVERLAPPED<\/code>\nand one to the OTHERDATA<\/code>).\nWe can just use a single OVERLAPPEDEX<\/code> pointer\nand dereference either the Overlapped<\/code>\nor the OtherData<\/code> part.\n<\/p>\n
\nOVERLAPPEDEX* FindOverlappedExFromOverlapped(\n    OVERLAPPED *lpOverlapped)\n{\n for (int index = 0; index < MAX_OVERLAPPED; index++) {\n  if (&Master[index].Overlapped == lpOverlapped) {\n   return &Master[index];\n  }\n }\n FatalError(); \/\/ should never be reached\n}\nvoid CALLBACK CompletionRoutine(\n    DWORD dwErrorCode,\n    DWORD dwNumberOfBytesTransferred,\n    LPOVERLAPPED lpOverlapped)\n{\n    OVELRAPPEDEX *lpOverlappedEx =\n                    FindOverlappedExFromOverlapped(lpOverlapped);\n    ... do stuff with lpOverlappedEx ...\n}\n<\/pre>\n
\nFinally, we can optimize the\nFindOverlappedExFromOverlapped<\/code> function\nthat we de-optimized earlier.\nObserve that the de-optimized loop is an example of the\n“for\/if” anti-pattern.\n<\/p>\n
\nThe “for\/if” anti-pattern goes like this:\n<\/p>\n
\nfor (int i = 0; i < 100; i++) {\n if (i == 42) do_something(i);\n}\n<\/pre>\n
\nThis can naturally be simplified to\n<\/p>\n
\ndo_something(42);\n<\/pre>\n
\nOur\nFindOverlappedExFromOverlapped<\/code> function\nis a special case of this anti-pattern.\nIt becomes more evident if we do some rewriting.\nStart with\n<\/p>\n
\n&Master[index].Overlapped == lpOverlapped\n<\/pre>\n
\nApply CONTAINING_RECORD<\/code> to both sides.\n<\/p>\n
\nCONTAINING_RECORD(&Master[index].Overlapped, OVERLAPPEDEX, Overlapped) ==\n    CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped)\n<\/pre>\n
\nThe left-hand side of the comparison simplifies to\n<\/p>\n
\n    &Master[index]\n<\/pre>\n
\nresulting in\n<\/p>\n
\n&Master[index] ==\n   CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped)\n<\/pre>\n
\nRecall that a[b]<\/code> is equivalent to *(a+b)<\/code>,\nand therefore &a[b]<\/code> is equivalent to a+b<\/code>.\n<\/p>\n
\nMaster + index ==\n   CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped)\n<\/pre>\n
Now subtract Master<\/code> from both sides:<\/p>\n
\nindex == CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped) - Master\n<\/pre>\n
\nWe have transformed the test into a clear case of the\nfor\/if anti-pattern,\nand the function can be simplified to\n<\/p>\n
\nOVERLAPPEDEX* FindOverlappedExFromOverlapped(\n    OVERLAPPED *lpOverlapped)\n{\n ptrdiff_t index =\n   CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped) - Master;\n return &Master[index];\n}\n<\/pre>\n
\nAgain, rewrite &a[b]<\/code> as a+b<\/code>:\n<\/p>\n
\n return Master + index;\n<\/pre>\n
\nSubstitute the value of index<\/code> computed on the previous\nline:\n<\/p>\n
\n return Master +\n   CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped) - Master;\n<\/pre>\n
\nThe two occurrences of Master<\/code> cancel out, leaving\n<\/p>\n
\nOVERLAPPEDEX* FindOverlappedExFromOverlapped(\n    OVERLAPPED *lpOverlapped)\n{\n return CONTAINING_RECORD(lpOverlapped, OVERLAPPEDEX, Overlapped);\n}\n<\/pre>\n
\nAnd there you have it.\nBy a series of purely mechanical transformations,\nwe have rediscovered the technique of\nextending the OVERLAPPED<\/code> structure.<\/p>\n","protected":false},"excerpt":{"rendered":"
You can take advantage of the fact that the OVERLAPPED associated with asynchronous I\/O is passed by address, but there was some confusion about how this technique could “work” when kernel mode has no idea that you are playing this trick. Whether kernel mode is in on the trick is immaterial since it is not […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-11963","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
You can take advantage of the fact that the OVERLAPPED associated with asynchronous I\/O is passed by address, but there was some confusion about how this technique could “work” when kernel mode has no idea that you are playing this trick. Whether kernel mode is in on the trick is immaterial since it is not […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/11963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=11963"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/11963\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=11963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=11963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=11963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}