Subversion Repositories Kolibri OS

Rev

Rev 3520 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. ; Implementation of periodic transaction scheduler for USB.
  2. ; Bandwidth dedicated to periodic transactions is limited, so
  3. ; different pipes should be scheduled as uniformly as possible.
  4.  
  5. ; USB1 scheduler.
  6. ; Algorithm is simple:
  7. ; when adding a pipe, optimize the following quantity:
  8. ;  * for every millisecond, take all bandwidth scheduled to periodic transfers,
  9. ;  * calculate maximum over all milliseconds,
  10. ;  * select a variant which minimizes that maximum;
  11. ; when removing a pipe, do nothing (except for bookkeeping).
  12.  
  13. ; sanity check: structures in UHCI and OHCI should be the same
  14. if (sizeof.ohci_static_ep=sizeof.uhci_static_ep)&(ohci_static_ep.SoftwarePart=uhci_static_ep.SoftwarePart)&(ohci_static_ep.NextList=uhci_static_ep.NextList)
  15. ; Select a list for a new pipe.
  16. ; in: esi -> usb_controller, maxpacket, type, interval can be found in the stack
  17. ; in: ecx = 2 * maximal interval = total number of periodic lists + 1
  18. ; in: edx -> {u|o}hci_static_ep for the first list
  19. ; in: eax -> byte past {u|o}hci_static_ep for the last list in the first group
  20. ; out: edx -> usb_static_ep for the selected list or zero if failed
  21. proc usb1_select_interrupt_list
  22. ; inherit some variables from usb_open_pipe
  23. virtual at ebp-8
  24. .bandwidth      dd      ?
  25. .target         dd      ?
  26.                 dd      ?
  27.                 dd      ?
  28. .config_pipe    dd      ?
  29. .endpoint       dd      ?
  30. .maxpacket      dd      ?
  31. .type           dd      ?
  32. .interval       dd      ?
  33. end virtual
  34.         push    ebx edi         ; save used registers to be stdcall
  35.         push    eax             ; save eax for checks in step 3
  36. ; 1. Only intervals 2^k ms can be supported.
  37. ; The core specification says that the real interval should not be greater
  38. ; than the interval given by the endpoint descriptor, but can be less.
  39. ; Determine the actual interval as 2^k ms.
  40.         mov     eax, ecx
  41. ; 1a. Set [.interval] to 1 if it was zero; leave it as is otherwise
  42.         cmp     [.interval], 1
  43.         adc     [.interval], 0
  44. ; 1b. Divide ecx by two while it is strictly greater than [.interval].
  45. @@:
  46.         shr     ecx, 1
  47.         cmp     [.interval], ecx
  48.         jb      @b
  49. ; ecx = the actual interval
  50. ;
  51. ; For example, let ecx = 8, eax = 64.
  52. ; The scheduler space is 32 milliseconds,
  53. ; we need to schedule something every 8 ms;
  54. ; there are 8 variants: schedule at times 0,8,16,24,
  55. ; schedule at times 1,9,17,25,..., schedule at times 7,15,23,31.
  56. ; Now concentrate: there are three nested loops,
  57. ; * the innermost loop calculates the total periodic bandwidth scheduled
  58. ;   in the given millisecond,
  59. ; * the intermediate loop calculates the maximum over all milliseconds
  60. ;   in the given variant, that is the quantity we're trying to minimize,
  61. ; * the outermost loop checks all variants.
  62. ; 2. Calculate offset between the first list and the first list for the
  63. ; selected interval, in bytes; save in the stack for step 4.
  64.         sub     eax, ecx
  65.         sub     eax, ecx
  66.         imul    eax, sizeof.ohci_static_ep
  67.         push    eax
  68.         imul    ebx, ecx, sizeof.ohci_static_ep
  69. ; 3. Select the best variant.
  70. ; 3a. The outermost loop.
  71. ; Prepare for the loop: set the current optimal bandwidth to maximum
  72. ; possible value (so that any variant will pass the first comparison),
  73. ; calculate delta for the intermediate loop.
  74.         or      [.bandwidth], -1
  75. .varloop:
  76. ; 3b. The intermediate loop.
  77. ; Prepare for the loop: set the maximum to be calculated to zero,
  78. ; save counter of the outermost loop.
  79.         xor     edi, edi
  80.         push    edx
  81. virtual at esp
  82. .cur_variant    dd      ?       ; step 3b
  83. .result_delta   dd      ?       ; step 2
  84. .group1_limit   dd      ?       ; function prolog
  85. end virtual
  86. .calc_max_bandwidth:
  87. ; 3c. The innermost loop. Sum over all lists.
  88.         xor     eax, eax
  89.         push    edx
  90. .calc_bandwidth:
  91.         add     eax, [edx+ohci_static_ep.SoftwarePart+usb_static_ep.Bandwidth]
  92.         mov     edx, [edx+ohci_static_ep.NextList]
  93.         test    edx, edx
  94.         jnz     .calc_bandwidth
  95.         pop     edx
  96. ; 3d. The intermediate loop continued: update maximum.
  97.         cmp     eax, edi
  98.         jb      @f
  99.         mov     edi, eax
  100. @@:
  101. ; 3e. The intermediate loop continued: advance counter.
  102.         add     edx, ebx
  103.         cmp     edx, [.group1_limit]
  104.         jb      .calc_max_bandwidth
  105. ; 3e. The intermediate loop done: restore counter of the outermost loop.
  106.         pop     edx
  107. ; 3f. The outermost loop continued: if the current variant is
  108. ; better (maybe not strictly) then the previous optimum, update
  109. ; the optimal bandwidth and resulting list.
  110.         cmp     edi, [.bandwidth]
  111.         ja      @f
  112.         mov     [.bandwidth], edi
  113.         mov     [.target], edx
  114. @@:
  115. ; 3g. The outermost loop continued: advance counter.
  116.         add     edx, sizeof.ohci_static_ep
  117.         dec     ecx
  118.         jnz     .varloop
  119. ; 4. Get the pointer to the best list.
  120.         pop     edx             ; restore value from step 2
  121.         pop     eax             ; purge stack var from prolog
  122.         add     edx, [.target]
  123. ; 5. Calculate bandwidth for the new pipe.
  124.         mov     eax, [.maxpacket]       ; TODO: calculate real bandwidth
  125.         and     eax, (1 shl 11) - 1
  126. ; 6. TODO: check that bandwidth for the new pipe plus old bandwidth
  127. ; still fits to maximum allowed by the core specification.
  128. ; 7. Convert {o|u}hci_static_ep to usb_static_ep, update bandwidth and return.
  129.         add     edx, ohci_static_ep.SoftwarePart
  130.         add     [edx+usb_static_ep.Bandwidth], eax
  131.         pop     edi ebx         ; restore used registers to be stdcall
  132.         ret
  133. endp
  134. ; sanity check, part 2
  135. else
  136. .err select_interrupt_list must be different for UHCI and OHCI
  137. end if
  138.  
  139. ; Pipe is removing, update the corresponding lists.
  140. ; We do not reorder anything, so just update book-keeping variable
  141. ; in the list header.
  142. proc usb1_interrupt_list_unlink
  143. virtual at esp
  144.                 dd      ?       ; return address
  145. .maxpacket      dd      ?
  146. .lowspeed       db      ?
  147. .direction      db      ?
  148.                 rb      2
  149. end virtual
  150. ; find list header
  151.         mov     edx, ebx
  152. @@:
  153.         mov     edx, [edx+usb_pipe.NextVirt]
  154.         cmp     [edx+usb_pipe.Controller], esi
  155.         jnz     @b
  156. ; subtract pipe bandwidth
  157. ; TODO: calculate real bandwidth
  158.         mov     eax, [.maxpacket]
  159.         and     eax, (1 shl 11) - 1
  160.         sub     [edx+usb_static_ep.Bandwidth], eax
  161.         ret     8
  162. endp
  163.  
  164. ; USB2 scheduler.
  165. ; There are two parts: high-speed pipes and split-transaction pipes.
  166. ; Split-transaction scheduler is currently a stub.
  167. ; High-speed scheduler uses the same algorithm as USB1 scheduler:
  168. ; when adding a pipe, optimize the following quantity:
  169. ;  * for every microframe, take all bandwidth scheduled to periodic transfers,
  170. ;  * calculate maximum over all microframe,
  171. ;  * select a variant which minimizes that maximum;
  172. ; when removing a pipe, do nothing (except for bookkeeping).
  173. ; in: esi -> usb_controller
  174. ; out: edx -> usb_static_ep, eax = S-Mask
  175. proc ehci_select_hs_interrupt_list
  176. ; inherit some variables from usb_open_pipe
  177. virtual at ebp-12
  178. .targetsmask    dd      ?
  179. .bandwidth      dd      ?
  180. .target         dd      ?
  181.                 dd      ?
  182.                 dd      ?
  183. .config_pipe    dd      ?
  184. .endpoint       dd      ?
  185. .maxpacket      dd      ?
  186. .type           dd      ?
  187. .interval       dd      ?
  188. end virtual
  189. ; prolog, initialize local vars
  190.         or      [.bandwidth], -1
  191.         or      [.target], -1
  192.         or      [.targetsmask], -1
  193.         push    ebx edi         ; save used registers to be stdcall
  194. ; 1. In EHCI, every list describes one millisecond = 8 microframes.
  195. ; Thus, there are two significantly different branches:
  196. ; for pipes with interval >= 8 microframes, advance to 2,
  197. ; for pipes which should be planned in every frame (one or more microframes),
  198. ; go to 9.
  199. ; Note: the actual interval for high-speed devices is 2^([.interval]-1),
  200. ; (the core specification forbids [.interval] == 0)
  201.         mov     ecx, [.interval]
  202.         dec     ecx
  203.         cmp     ecx, 3
  204.         jb      .every_frame
  205. ; 2. Determine the actual interval in milliseconds.
  206.         sub     ecx, 3
  207.         cmp     ecx, 5  ; maximum 32ms
  208.         jbe     @f
  209.         movi    ecx, 5
  210. @@:
  211. ; There are four nested loops,
  212. ; * Loop #4 (the innermost one) calculates the total periodic bandwidth
  213. ;   scheduled in the given microframe of the given millisecond.
  214. ; * Loop #3 calculates the maximum over all milliseconds
  215. ;   in the given variant, that is the quantity we're trying to minimize.
  216. ; * Loops #1 and #2 check all variants;
  217. ;   loop #1 is responsible for the target millisecond,
  218. ;   loop #2 is responsible for the microframe within millisecond.
  219. ; 3. Prepare for loops.
  220. ; ebx = number of iterations of loop #1
  221. ; [esp] = delta of counter for loop #3, in bytes
  222. ; [esp+4] = delta between the first group and the target group, in bytes
  223.         movi    ebx, 1
  224.         movi    edx, sizeof.ehci_static_ep
  225.         shl     ebx, cl
  226.         shl     edx, cl
  227.         mov     eax, 64*sizeof.ehci_static_ep
  228.         sub     eax, edx
  229.         sub     eax, edx
  230.         push    eax
  231.         push    edx
  232. ; 4. Select the best variant.
  233. ; 4a. Loop #1: initialize counter = pointer to ehci_static_ep for
  234. ; the target millisecond in the first group.
  235.         lea     edx, [esi+ehci_controller.IntEDs-sizeof.ehci_controller]
  236. .varloop0:
  237. ; 4b. Loop #2: initialize counter = microframe within the target millisecond.
  238.         xor     ecx, ecx
  239. .varloop:
  240. ; 4c. Loop #3: save counter of loop #1,
  241. ; initialize counter with the value of loop #1 counter,
  242. ; initialize maximal bandwidth = zero.
  243.         xor     edi, edi
  244.         push    edx
  245. virtual at esp
  246. .saved_counter1         dd      ?       ; step 4c
  247. .loop3_delta            dd      ?       ; step 3
  248. .target_delta           dd      ?       ; step 3
  249. end virtual
  250. .calc_max_bandwidth:
  251. ; 4d. Loop #4: initialize counter with the value of loop #3 counter,
  252. ; initialize total bandwidth = zero.
  253.         xor     eax, eax
  254.         push    edx
  255. .calc_bandwidth:
  256. ; 4e. Loop #4: add the bandwidth from the current list
  257. ; and advance to the next list, while there is one.
  258.         add     ax, [edx+ehci_static_ep.Bandwidths+ecx*2]
  259.         mov     edx, [edx+ehci_static_ep.NextList]
  260.         test    edx, edx
  261.         jnz     .calc_bandwidth
  262. ; 4f. Loop #4 end: restore counter of loop #3.
  263.         pop     edx
  264. ; 4g. Loop #3: update maximal bandwidth.
  265.         cmp     eax, edi
  266.         jb      @f
  267.         mov     edi, eax
  268. @@:
  269. ; 4h. Loop #3: advance the counter and repeat while within the first group.
  270.         lea     eax, [esi+ehci_controller.IntEDs+32*sizeof.ehci_static_ep-sizeof.ehci_controller]
  271.         add     edx, [.loop3_delta]
  272.         cmp     edx, eax
  273.         jb      .calc_max_bandwidth
  274. ; 4i. Loop #3 end: restore counter of loop #1.
  275.         pop     edx
  276. ; 4j. Loop #2: if the current variant is better (maybe not strictly)
  277. ; then the previous optimum, update the optimal bandwidth and the target.
  278.         cmp     edi, [.bandwidth]
  279.         ja      @f
  280.         mov     [.bandwidth], edi
  281.         mov     [.target], edx
  282.         movi    eax, 1
  283.         shl     eax, cl
  284.         mov     [.targetsmask], eax
  285. @@:
  286. ; 4k. Loop #2: continue 8 times for every microframe.
  287.         inc     ecx
  288.         cmp     ecx, 8
  289.         jb      .varloop
  290. ; 4l. Loop #1: advance counter and repeat ebx times,
  291. ; ebx was calculated in step 3.
  292.         add     edx, sizeof.ehci_static_ep
  293.         dec     ebx
  294.         jnz     .varloop0
  295. ; 5. Get the pointer to the best list.
  296.         pop     edx             ; restore value from step 3
  297.         pop     edx             ; get delta calculated in step 3
  298.         add     edx, [.target]
  299. ; 6. Calculate bandwidth for the new pipe.
  300. ; TODO1: calculate real bandwidth
  301.         mov     eax, [.maxpacket]
  302.         mov     ecx, eax
  303.         and     eax, (1 shl 11) - 1
  304.         shr     ecx, 11
  305.         inc     ecx
  306.         and     ecx, 3
  307.         imul    eax, ecx
  308. ; 7. TODO2: check that bandwidth for the new pipe plus old bandwidth
  309. ; still fits to maximum allowed by the core specification
  310. ; current [.bandwidth] + new bandwidth <= limit;
  311. ; USB2 specification allows maximum 60000*80% bit times for periodic microframe
  312. ; 8. Convert {o|u}hci_static_ep to usb_static_ep, update bandwidth and return.
  313.         mov     ecx, [.targetsmask]
  314.         add     [edx+ehci_static_ep.Bandwidths+ecx*2], ax
  315.         add     edx, ehci_static_ep.SoftwarePart
  316.         movi    eax, 1
  317.         shl     eax, cl
  318.         pop     edi ebx         ; restore used registers to be stdcall
  319.         ret
  320. .every_frame:
  321. ; The pipe should be scheduled every frame in two or more microframes.
  322. ; 9. Calculate maximal bandwidth for every microframe: three nested loops.
  323. ; 9a. The outermost loop: ebx = microframe to calculate.
  324.         xor     ebx, ebx
  325. .calc_all_bandwidths:
  326. ; 9b. The intermediate loop:
  327. ; edx = pointer to ehci_static_ep in the first group, [esp] = counter,
  328. ; edi = maximal bandwidth
  329.         lea     edx, [esi+ehci_controller.IntEDs-sizeof.ehci_controller]
  330.         xor     edi, edi
  331.         push    32
  332. .calc_max_bandwidth2:
  333. ; 9c. The innermost loop: calculate bandwidth for the given microframe
  334. ; in the given frame.
  335.         xor     eax, eax
  336.         push    edx
  337. .calc_bandwidth2:
  338.         add     ax, [edx+ehci_static_ep.Bandwidths+ebx*2]
  339.         mov     edx, [edx+ehci_static_ep.NextList]
  340.         test    edx, edx
  341.         jnz     .calc_bandwidth2
  342.         pop     edx
  343. ; 9d. The intermediate loop continued: update maximal bandwidth.
  344.         cmp     eax, edi
  345.         jb      @f
  346.         mov     edi, eax
  347. @@:
  348.         add     edx, sizeof.ehci_static_ep
  349.         dec     dword [esp]
  350.         jnz     .calc_max_bandwidth2
  351.         pop     eax
  352. ; 9e. Push the calculated maximal bandwidth and continue the outermost loop.
  353.         push    edi
  354.         inc     ebx
  355.         cmp     ebx, 8
  356.         jb      .calc_all_bandwidths
  357. virtual at esp
  358. .bandwidth7     dd      ?
  359. .bandwidth6     dd      ?
  360. .bandwidth5     dd      ?
  361. .bandwidth4     dd      ?
  362. .bandwidth3     dd      ?
  363. .bandwidth2     dd      ?
  364. .bandwidth1     dd      ?
  365. .bandwidth0     dd      ?
  366. end virtual
  367. ; 10. Select the best variant.
  368. ; edx = S-Mask = bitmask of scheduled microframes
  369.         movi    edx, 0x11
  370.         cmp     ecx, 1
  371.         ja      @f
  372.         mov     dl, 0x55
  373.         jz      @f
  374.         mov     dl, 0xFF
  375. @@:
  376. ; try all variants edx, edx shl 1, edx shl 2, ...
  377. ; until they fit in the lower byte (8 microframes per frame)
  378. .select_best_mframe:
  379.         xor     edi, edi
  380.         mov     ecx, edx
  381.         mov     eax, esp
  382. .calc_mframe:
  383.         add     cl, cl
  384.         jnc     @f
  385.         cmp     edi, [eax]
  386.         jae     @f
  387.         mov     edi, [eax]
  388. @@:
  389.         add     eax, 4
  390.         test    cl, cl
  391.         jnz     .calc_mframe
  392.         cmp     [.bandwidth], edi
  393.         jb      @f
  394.         mov     [.bandwidth], edi
  395.         mov     [.targetsmask], edx
  396. @@:
  397.         add     dl, dl
  398.         jnc     .select_best_mframe
  399. ; 11. Restore stack after step 9.
  400.         add     esp, 8*4
  401. ; 12. Get the pointer to the target list (responsible for every microframe).
  402.         lea     edx, [esi+ehci_controller.IntEDs.SoftwarePart+62*sizeof.ehci_static_ep-sizeof.ehci_controller]
  403. ; 13. TODO1: calculate real bandwidth.
  404.         mov     eax, [.maxpacket]
  405.         mov     ecx, eax
  406.         and     eax, (1 shl 11) - 1
  407.         shr     ecx, 11
  408.         inc     ecx
  409.         and     ecx, 3
  410.         imul    eax, ecx
  411. ; 14. TODO2: check that current [.bandwidth] + new bandwidth <= limit;
  412. ; USB2 specification allows maximum 60000*80% bit times for periodic microframe.
  413. ; Update bandwidths including the new pipe.
  414.         mov     ecx, [.targetsmask]
  415.         lea     edi, [edx+ehci_static_ep.Bandwidths-ehci_static_ep.SoftwarePart]
  416. .update_bandwidths:
  417.         shr     ecx, 1
  418.         jnc     @f
  419.         add     [edi], ax
  420. @@:
  421.         add     edi, 2
  422.         test    ecx, ecx
  423.         jnz     .update_bandwidths
  424. ; 15. Return target list and target S-Mask.
  425.         mov     eax, [.targetsmask]
  426.         pop     edi ebx         ; restore used registers to be stdcall
  427.         ret
  428. endp
  429.  
  430. ; Pipe is removing, update the corresponding lists.
  431. ; We do not reorder anything, so just update book-keeping variable
  432. ; in the list header.
  433. proc ehci_hs_interrupt_list_unlink
  434. ; get target list
  435.         mov     edx, [ebx+ehci_pipe.BaseList-ehci_pipe.SoftwarePart]
  436. ; TODO: calculate real bandwidth
  437.         movzx   eax, word [ebx+ehci_pipe.Token-ehci_pipe.SoftwarePart+2]
  438.         mov     ecx, [ebx+ehci_pipe.Flags-ehci_pipe.SoftwarePart]
  439.         and     eax, (1 shl 11) - 1
  440.         shr     ecx, 30
  441.         imul    eax, ecx
  442.         movzx   ecx, byte [ebx+ehci_pipe.Flags-ehci_pipe.SoftwarePart]
  443.         add     edx, ehci_static_ep.Bandwidths - ehci_static_ep.SoftwarePart
  444. ; update bandwidth
  445. .dec_bandwidth:
  446.         shr     ecx, 1
  447.         jnc     @f
  448.         sub     [edx], ax
  449. @@:
  450.         add     edx, 2
  451.         test    ecx, ecx
  452.         jnz     .dec_bandwidth
  453. ; return
  454.         ret
  455. endp
  456.  
  457. uglobal
  458. ehci_last_fs_alloc      dd      ?
  459. endg
  460.  
  461. ; This needs to be rewritten. Seriously.
  462. ; It schedules everything to the first microframe of some frame,
  463. ; frame is spinned out of thin air.
  464. ; This works while you have one keyboard and one mouse...
  465. ; maybe even ten keyboards and ten mice... but give any serious stress,
  466. ; and this would break.
  467. proc ehci_select_fs_interrupt_list
  468. virtual at ebp-12
  469. .targetsmask    dd      ?
  470. .bandwidth      dd      ?
  471. .target         dd      ?
  472.                 dd      ?
  473.                 dd      ?
  474. .config_pipe    dd      ?
  475. .endpoint       dd      ?
  476. .maxpacket      dd      ?
  477. .type           dd      ?
  478. .interval       dd      ?
  479. end virtual
  480.         cmp     [.interval], 1
  481.         adc     [.interval], 0
  482.         mov     ecx, 64
  483.         mov     eax, ecx
  484. @@:
  485.         shr     ecx, 1
  486.         cmp     [.interval], ecx
  487.         jb      @b
  488.         sub     eax, ecx
  489.         sub     eax, ecx
  490.         dec     ecx
  491.         and     ecx, [ehci_last_fs_alloc]
  492.         inc     [ehci_last_fs_alloc]
  493.         add     eax, ecx
  494.         imul    eax, sizeof.ehci_static_ep
  495.         lea     edx, [esi+ehci_controller.IntEDs.SoftwarePart+eax-sizeof.ehci_controller]
  496.         mov     ax, 1C01h
  497.         ret
  498. endp
  499.  
  500. proc ehci_fs_interrupt_list_unlink
  501.         ret
  502. endp
  503.