Windows System Software -- Consulting, Training, Development -- Unique Expertise, Guaranteed Results

Before Posting...
Please check out the Community Guidelines in the Announcements and Administration Category.

Re: overlapped request ordering

Ken_JohnsonKen_Johnson Member - All Emails Posts: 1,559
No, do not use sequence numbers, please. It's a broken design, IMO; consider how to handle wrapping when the input queue size is unbounded. Instead, place the requets in an ordered queue.

? S

-----Original Message-----
From: Maxim S. Shatskih
Sent: Thursday, January 22, 2009 09:02
To: Windows System Software Devs Interest List
Subject: Re:[ntdev] Overlapped IO Sequencing


> When the requests get back to the application they are out of order.

This is normal and by design.

Assign sequence numbers to the requests, and then reassemble the completed requests in the number order.

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


---
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

? S

Comments

  • Michal_Vodicka-2Michal_Vodicka-2 Member Posts: 1,612
    Yes, that's really easy and straightforward. Once queued, you can always
    wait for the queue head request completion and don't need to care about
    other requests.

    Best regards,

    Michal Vodicka
    UPEK, Inc.
    [xxxxx@upek.com, http://www.upek.com ]




    ________________________________

    From: xxxxx@lists.osr.com
    [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 7:00 PM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] overlapped request ordering



    No, do not use sequence numbers, please. It's a broken design,
    IMO; consider how to handle wrapping when the input queue size is
    unbounded. Instead, place the requets in an ordered queue.

    - S

    -----Original Message-----
    From: Maxim S. Shatskih
    Sent: Thursday, January 22, 2009 09:02
    To: Windows System Software Devs Interest List

    Subject: Re:[ntdev] Overlapped IO Sequencing


    > When the requests get back to the application they are out of
    order.

    This is normal and by design.

    Assign sequence numbers to the requests, and then reassemble the
    completed requests in the number order.

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


    ---
    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

    - S
    ---
    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
  • Maxim_S._ShatskihMaxim_S._Shatskih Member Posts: 10,396
    >No, do not use sequence numbers, please. It's a broken design, IMO; consider how to handle
    >wrapping when the input queue size is unbounded

    TCP uses wrapping sequence numbers for 25 years or such.

    --
    Maxim S. Shatskih
    Windows DDK MVP
    xxxxx@storagecraft.com
    http://www.storagecraft.com
  • Mark_S._EdwardsMark_S._Edwards Member Posts: 475
    At 22:28 22/01/2009, Maxim S. Shatskih wrote:
    > >No, do not use sequence numbers, please. It's a broken design,
    > IMO; consider how to handle
    > >wrapping when the input queue size is unbounded
    >
    >TCP uses wrapping sequence numbers for 25 years or such.

    That was an understandable solution when networks ran in
    kilobits. Today it's a problem on 10 Gb/s and above networks, the
    sequence number can wrap too quickly.
  • Ken_JohnsonKen_Johnson Member - All Emails Posts: 1,559
    Yes, with problems that need gross hacks to ensure that it "mostly works" on fast (e.g. 10GbE) environments; timestamps had to be added in to be considered along with sequence numbers. It is not a preferable design when trivially avoidable with a cheap alternative.

    ? S

    -----Original Message-----
    From: Maxim S. Shatskih <xxxxx@storagecraft.com>
    Sent: Thursday, January 22, 2009 14:30
    To: Windows System Software Devs Interest List <xxxxx@lists.osr.com>
    Subject: Re:[ntdev] overlapped request ordering


    >No, do not use sequence numbers, please. It's a broken design, IMO; consider how to handle
    >wrapping when the input queue size is unbounded

    TCP uses wrapping sequence numbers for 25 years or such.

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


    ---
    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
  • OSR_Community_UserOSR_Community_User Member Posts: 110,217
    If I use a 32-bit number, I need 4.2GIRPs before it wraps. That can take a
    while. But if I want to be conservative, I can use 64-bit sequence numbers,
    and realistically it becomes a non-issue.
    joe

    _____

    From: xxxxx@lists.osr.com
    [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 1:00 PM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] overlapped request ordering



    No, do not use sequence numbers, please. It's a broken design, IMO; consider
    how to handle wrapping when the input queue size is unbounded. Instead,
    place the requets in an ordered queue.

    - S

    -----Original Message-----
    From: Maxim S. Shatskih
    Sent: Thursday, January 22, 2009 09:02
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Overlapped IO Sequencing


    > When the requests get back to the application they are out of order.

    This is normal and by design.

    Assign sequence numbers to the requests, and then reassemble the completed
    requests in the number order.

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


    ---
    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

    - S
    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
  • Ken_JohnsonKen_Johnson Member - All Emails Posts: 1,559
    Why would you use a sequence-based algorithm when there?s an efficient alternative?

    - S

    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
    Sent: Thursday, January 22, 2009 11:38 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering

    If I use a 32-bit number, I need 4.2GIRPs before it wraps. That can take a while. But if I want to be conservative, I can use 64-bit sequence numbers, and realistically it becomes a non-issue.
    joe

    ________________________________
    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 1:00 PM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] overlapped request ordering

    No, do not use sequence numbers, please. It's a broken design, IMO; consider how to handle wrapping when the input queue size is unbounded. Instead, place the requets in an ordered queue.

    ? S

    -----Original Message-----
    From: Maxim S. Shatskih
    Sent: Thursday, January 22, 2009 09:02
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Overlapped IO Sequencing


    > When the requests get back to the application they are out of order.

    This is normal and by design.

    Assign sequence numbers to the requests, and then reassemble the completed requests in the number order.

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


    ---
    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

    ? S
    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
    ---
    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
  • OSR_Community_UserOSR_Community_User Member Posts: 110,217
    But I've not seen a proposal for an "efficient alternative". At the user
    API level, the reading seems to be that there is no ordering guarantee
    between the issuance of an IRP and its subsequent receipt, for example, at
    an I/O Completion Port. If I issue IRPs in the order A, B, C, my
    understanding is that even for a simple device driver that completes the
    IRPs in FIFO order, I have no guarantee that I will receive them in the
    order A, B, C. This is somewhat disturbing for stream-oriented devices such
    as serial ports (limiting the sequencing to a single direction on the port;
    obviously if I have read and write operations they run independently of each
    other), and for the device I was using, which has a single FIFO queue that
    it processes sequentially.
    joe

    _____

    From: xxxxx@lists.osr.com
    [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 11:40 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering



    Why would you use a sequence-based algorithm when there's an efficient
    alternative?



    - S



    From: xxxxx@lists.osr.com
    [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
    Sent: Thursday, January 22, 2009 11:38 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering



    If I use a 32-bit number, I need 4.2GIRPs before it wraps. That can take a
    while. But if I want to be conservative, I can use 64-bit sequence numbers,
    and realistically it becomes a non-issue.

    joe



    _____

    From: xxxxx@lists.osr.com
    [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 1:00 PM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] overlapped request ordering


    No, do not use sequence numbers, please. It's a broken design, IMO; consider
    how to handle wrapping when the input queue size is unbounded. Instead,
    place the requets in an ordered queue.

    - S

    -----Original Message-----
    From: Maxim S. Shatskih
    Sent: Thursday, January 22, 2009 09:02
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Overlapped IO Sequencing


    > When the requests get back to the application they are out of order.

    This is normal and by design.

    Assign sequence numbers to the requests, and then reassemble the completed
    requests in the number order.

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


    ---
    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

    - S
    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
    ---
    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


    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
  • Ken_JohnsonKen_Johnson Member - All Emails Posts: 1,559
    Okay, restating again:

    Push your OVERLAPPED-derived structure on a queue when you submit the request.

    When you receive a completion indication, see if the queue head is the current item being completed. If not, set a flag in the current item?s OVERLAPPED-derived structure indicating that it?s finished. Otherwise, process completion for the current item and remove it from the queue. Then, while subsequent items in the queue are flagged as finished, continue processing them and removing them from the queue.

    - S

    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
    Sent: Thursday, January 22, 2009 11:50 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering

    But I've not seen a proposal for an "efficient alternative". At the user API level, the reading seems to be that there is no ordering guarantee between the issuance of an IRP and its subsequent receipt, for example, at an I/O Completion Port. If I issue IRPs in the order A, B, C, my understanding is that even for a simple device driver that completes the IRPs in FIFO order, I have no guarantee that I will receive them in the order A, B, C. This is somewhat disturbing for stream-oriented devices such as serial ports (limiting the sequencing to a single direction on the port; obviously if I have read and write operations they run independently of each other), and for the device I was using, which has a single FIFO queue that it processes sequentially.
    joe

    ________________________________
    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 11:40 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering
    Why would you use a sequence-based algorithm when there?s an efficient alternative?

    - S

    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Joseph M. Newcomer
    Sent: Thursday, January 22, 2009 11:38 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] overlapped request ordering

    If I use a 32-bit number, I need 4.2GIRPs before it wraps. That can take a while. But if I want to be conservative, I can use 64-bit sequence numbers, and realistically it becomes a non-issue.
    joe

    ________________________________
    From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Skywing
    Sent: Thursday, January 22, 2009 1:00 PM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] overlapped request ordering

    No, do not use sequence numbers, please. It's a broken design, IMO; consider how to handle wrapping when the input queue size is unbounded. Instead, place the requets in an ordered queue.

    ? S

    -----Original Message-----
    From: Maxim S. Shatskih
    Sent: Thursday, January 22, 2009 09:02
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Overlapped IO Sequencing


    > When the requests get back to the application they are out of order.

    This is normal and by design.

    Assign sequence numbers to the requests, and then reassemble the completed requests in the number order.

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


    ---
    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

    ? S
    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
    ---
    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

    ---
    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
    --
    This message has been scanned for viruses and
    dangerous content by MailScanner, and is
    believed to be clean.
    ---
    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
  • Pavel_APavel_A Member Posts: 2,674
    Skywing wrote:
    >
    > Okay, restating again:
    >
    > Push your OVERLAPPED-derived structure on a queue when you submit the
    > request.
    >
    > When you receive a completion indication, see if the queue head is the
    > current item being completed. If not, set a flag in the current item?s
    > OVERLAPPED-derived structure indicating that it?s finished. Otherwise,
    > process completion for the current item and remove it from the queue.
    > Then, while subsequent items in the queue are flagged as finished,
    > continue processing them and removing them from the queue.

    also, care should be taken to avoid starvation of the driver:
    Suppose 3 queued requests are completed by driver in
    order 1,2,3 and the app sees completions in order 3,2,1.
    If the app waits for #1 completed,
    it won't consume and re-submit #2,3,
    so the driver won't have a free buffer if new data arrives.

    regards,
    --pa
  • Michal_Vodicka-2Michal_Vodicka-2 Member Posts: 1,612
    > -----Original Message-----
    > From: xxxxx@lists.osr.com
    > [mailto:xxxxx@lists.osr.com] On Behalf Of Pavel A.
    > Sent: Friday, January 23, 2009 1:32 PM
    > To: Windows System Software Devs Interest List
    > Subject: Re:[ntdev] overlapped request ordering
    >
    > Skywing wrote:
    > >
    > > Okay, restating again:
    > >
    > > Push your OVERLAPPED-derived structure on a queue when you
    > submit the
    > > request.
    > >
    > > When you receive a completion indication, see if the queue
    > head is the
    > > current item being completed. If not, set a flag in the
    > current item's
    > > OVERLAPPED-derived structure indicating that it's finished.
    > Otherwise,
    > > process completion for the current item and remove it from
    > the queue.
    > > Then, while subsequent items in the queue are flagged as finished,
    > > continue processing them and removing them from the queue.
    >
    > also, care should be taken to avoid starvation of the driver:
    > Suppose 3 queued requests are completed by driver in
    > order 1,2,3 and the app sees completions in order 3,2,1.
    > If the app waits for #1 completed,
    > it won't consume and re-submit #2,3,
    > so the driver won't have a free buffer if new data arrives.

    Not a big deal, IMO. If all 3 requests are already completed, wait for
    request #1 will suffice very quickly.

    Actually, I use this way for implementing circular buffer (using 3
    queues) sitting between app and the driver and I'm really happy with
    this approach. It is simple, efficient and rather easy to implement.
    Driver starvation can be avoided by raising the length of submitted
    requests queue.

    Best regards,

    Michal Vodicka
    UPEK, Inc.
    [xxxxx@upek.com, http://www.upek.com]
  • Pavel_APavel_A Member Posts: 2,674
    Michal Vodicka wrote:
    ....
    > If all 3 requests are already completed, wait for
    > request #1 will suffice very quickly.

    cross your fingers. --pa
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Upcoming OSR Seminars
Developing Minifilters 29 July 2019 OSR Seminar Space
Writing WDF Drivers 23 Sept 2019 OSR Seminar Space
Kernel Debugging 21 Oct 2019 OSR Seminar Space
Internals & Software Drivers 18 Nov 2019 Dulles, VA