{"id":96405,"date":"2017-06-16T07:00:00","date_gmt":"2017-06-16T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=96405"},"modified":"2019-03-13T01:12:59","modified_gmt":"2019-03-13T08:12:59","slug":"20170616-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20170616-00\/?p=96405","title":{"rendered":"Combining the work queue of distinct events, order not important, with an auto-reset event"},"content":{"rendered":"

Some time ago, I described a lock-free pattern for a work queue of distinct events, where the order of event processing is not important<\/a>. A customer was using a variation of this pattern, where they unlink the entire work queue in the consumer<\/code><\/a>, and combining it with an auto-reset event to signal the consumer thread that there is work to do. The general sketch is like this: <\/p>\n

\nSLIST_HEADER WorkQueue;\nHANDLE WorkAvailable;\n\nstruct alignas(MEMORY_ALLOCATION_ALIGNMENT)\nWorkItem : SLIST_ENTRY\n{\n    ... other stuff ...\n};\n\nvoid Initialize()\n{\n InitializeSListHeader(&WorkQueue);\n\n \/\/ Create an auto-reset event, initially unset.\n WorkAvailable = CreateEvent(nullptr, FALSE, FALSE,\n                             nullptr);<\/font>\n}\n\nvoid RequestWork(WorkItem* work)\n{\n if (InterlockedPushEntrySList(&WorkQueue, work)\n                                               == nullptr) {\n  SetEvent(WorkAvailable);<\/font>\n }\n}\n\nvoid ConsumeWork()\n{\n while (true) {\n  WaitForSingleObject(WorkAvailable, INFINITE);<\/font>\n  PSLIST_ENTRY entry = InterlockedFlushSList(&WorkQueue);\n  while (entry) {\n   ProcessWorkItem(static_cast<WorkItem*>(entry));\n   PSLIST_ENTRY nextEntry = entry->Next;\n   delete entry;\n   entry = nextEntry;\n  }\n }<\/font>\n}\n<\/pre>\n
The customer was looking for something lighter weight than a kernel event, however. <\/p>\n
Enter Wait­On­Address<\/code>. We could use our  ALT_AEVENT<\/code> structure as a drop-in replacement for the kernel event, but we can do better. <\/p>\n
We can use a LONG<\/code> as our data and use it to signal the consumer thread. <\/p>\n
\nSLIST_HEADER WorkQueue;\nLONG WorkAvailable;<\/font>\n\nstruct alignas(MEMORY_ALLOCATION_ALIGNMENT)\nWorkItem : SLIST_ENTRY\n{\n    ... other stuff ...\n};\n\nvoid Initialize()\n{\n InitializeSListHeader(&WorkQueue);\n\n WorkAvailable = 0;<\/font>\n}\n\nvoid RequestWork(WorkItem* work)\n{\n if (InterlockedPushEntrySList(&WorkQueue, work)\n                                               == nullptr) {\n  InterlockedIncrement(&WorkAvailable);\n  WakeByAddressSingle(&WorkAvailable);<\/font>\n }\n}\n\nvoid ConsumeWork()\n{\n LONG PreviousAvailable = 0;<\/font>\n while (true) {\n  WaitOnAddress(&WorkAvailable,\n                &PreviousAvailable,\n                sizeof(PreviousAvailable),\n                INFINITE);\n  PreviousAvailable = WorkAvailable;<\/font>\n  PSLIST_ENTRY entry = InterlockedFlushSList(&WorkQueue);\n  while (entry) {\n   ProcessWorkItem(static_cast<WorkItem*>(entry));\n   PSLIST_ENTRY nextEntry = entry->Next;\n   delete entry;\n   entry = nextEntry;\n  }\n }\n}\n<\/pre>\n
We replace our kernel handle with a LONG<\/code> that contains the number of times the consumer has been notified of work. The precise meaning of the value isn’t important; what’s important is that it changes whenever we want the consumer to wake up, and zero means that no work has ever been queued. <\/p>\n
The consumer waits for the counter to become nonzero, meaning that there might be some work. It captures the updated counter value, drains any available work, and then waits for the counter to change again. <\/p>\n
There are many ways this code could be structured, but it is important that we capture the counter before<\/i> draining the work. That way, if the counter changes while we are draining the work, our subsequent Wait­On­Address<\/code> will return immediately rather than waiting for the counter to change yet again. <\/p>\n
Note also that the code is resilent to spurious wake-ups. If the Wait­On­Address<\/code> returns prematurely, the code performs a redundant check for work. It won’t find any work, and will cycle back to wait for another change. <\/p>\n","protected":false},"excerpt":{"rendered":"
Combining two solutions into a bigger solution.<\/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-96405","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Combining two solutions into a bigger solution.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/96405","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=96405"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/96405\/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=96405"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=96405"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=96405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}