Subversion Repositories Kolibri OS

Rev

Rev 3555 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
3555 Serge 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
3626 Serge 209
        movi    ecx, 5
3555 Serge 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
3626 Serge 223
        movi    ebx, 1
224
        movi    edx, sizeof.ehci_static_ep
3555 Serge 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
3626 Serge 282
        movi    eax, 1
3555 Serge 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
3626 Serge 316
        movi    eax, 1
3555 Serge 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
3626 Serge 369
        movi    edx, 0x11
3555 Serge 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