1use alloc::boxed::Box;
31use core::cell::UnsafeCell;
32use core::sync::atomic::{AtomicI32, AtomicPtr, AtomicU32, AtomicU64, AtomicUsize, Ordering::SeqCst};
33
34use crate::{Sem, Thread, cpu_count, thread_spawn, thread_yield, wake};
35
36pub const THR_MAX: usize = 64;
37const SPIN_LOCK: u32 = 64; const SPIN_IDLE: u32 = 256; const SPIN_WAIT: u32 = 2000; const WAIT_POLL_MS: i32 = 2; const THR_STACK: usize = 0x10_0000; const JF_QUEUED: u32 = 1;
43const JF_ASYNC: u32 = 2;
44const TS_NONE: u32 = 0;
45const TS_INIT: u32 = 1;
46const TS_READY: u32 = 2;
47const TS_STOP: u32 = 3; const JS_RUNNING: u32 = 1;
49const JS_DONE: u32 = 2;
50const JS_STARTING: u32 = 3; #[derive(Debug, Clone, Copy, PartialEq, Eq)]
54pub struct Cancelled;
55
56type ItemFn = dyn Fn(usize, &JobCtl) + Sync;
57
58pub struct JobCtl {
60 f: UnsafeCell<*const ItemFn>, count: UnsafeCell<u64>, next: AtomicU64, done: AtomicU64, cancel: AtomicU32,
65 state: AtomicU32,
66 active: UnsafeCell<u32>, flags: UnsafeCell<u32>, link: UnsafeCell<*const JobCtl>, }
70
71unsafe impl Sync for JobCtl {}
74unsafe impl Send for JobCtl {}
75
76impl JobCtl {
77 fn new(f: *const ItemFn, count: u64) -> JobCtl {
78 JobCtl {
79 f: UnsafeCell::new(f),
80 count: UnsafeCell::new(count),
81 next: AtomicU64::new(0),
82 done: AtomicU64::new(0),
83 cancel: AtomicU32::new(0),
84 state: AtomicU32::new(0),
85 active: UnsafeCell::new(0),
86 flags: UnsafeCell::new(0),
87 link: UnsafeCell::new(core::ptr::null()),
88 }
89 }
90
91 pub fn cancel(&self) {
93 job_cancel(self)
94 }
95
96 pub fn cancelled(&self) -> bool {
98 self.cancel.load(SeqCst) != 0
99 }
100
101 pub fn count(&self) -> u64 {
102 unsafe { *self.count.get() }
104 }
105
106 pub fn items_done(&self) -> u64 {
108 self.done.load(SeqCst)
109 }
110
111 fn result(&self) -> Result<(), Cancelled> {
112 if self.cancel.load(SeqCst) != 0 { Err(Cancelled) } else { Ok(()) }
113 }
114}
115
116struct Pool {
119 lock: AtomicU32,
120 head: AtomicPtr<JobCtl>,
121 tail: AtomicPtr<JobCtl>,
122 work: UnsafeCell<Option<Sem>>, donesem: UnsafeCell<Option<Sem>>, dwait: AtomicI32,
125 state: AtomicU32,
126 n: AtomicU32,
127 quit: AtomicU32,
128 threads: UnsafeCell<[Option<Thread>; THR_MAX]>,
129 stk: [AtomicUsize; THR_MAX], }
131
132unsafe impl Sync for Pool {}
135
136static POOL: Pool = Pool {
137 lock: AtomicU32::new(0),
138 head: AtomicPtr::new(core::ptr::null_mut()),
139 tail: AtomicPtr::new(core::ptr::null_mut()),
140 work: UnsafeCell::new(None),
141 donesem: UnsafeCell::new(None),
142 dwait: AtomicI32::new(0),
143 state: AtomicU32::new(TS_NONE),
144 n: AtomicU32::new(0),
145 quit: AtomicU32::new(0),
146 threads: UnsafeCell::new([const { None }; THR_MAX]),
147 stk: [const { AtomicUsize::new(0) }; THR_MAX],
148};
149
150fn work_sem() -> Option<&'static Sem> {
151 unsafe { (*POOL.work.get()).as_ref() }
153}
154
155fn done_sem() -> Option<&'static Sem> {
156 unsafe { (*POOL.donesem.get()).as_ref() }
158}
159
160pub fn thr_init(n: u32) -> u32 {
162 loop {
163 if POOL.state.load(SeqCst) == TS_READY {
164 return POOL.n.load(SeqCst);
165 }
166 if POOL.state.compare_exchange(TS_NONE, TS_INIT, SeqCst, SeqCst).is_ok() {
167 break;
168 }
169 thread_yield(); }
171 let mut want = n as usize;
172 if let Some(v) = crate::arg_value("--threads").and_then(|v| v.parse::<i32>().ok()) {
173 if v > 0 {
174 want = v as usize;
175 }
176 }
177 if want == 0 {
178 want = cpu_count() as usize;
179 }
180 let want = want.min(THR_MAX);
181 POOL.quit.store(0, SeqCst);
182 POOL.head.store(core::ptr::null_mut(), SeqCst);
183 POOL.tail.store(core::ptr::null_mut(), SeqCst);
184 POOL.dwait.store(0, SeqCst);
185 let mut started = 0;
186 unsafe {
188 *POOL.work.get() = Sem::new(0);
189 *POOL.donesem.get() = Sem::new(0);
190 if work_sem().is_some() && done_sem().is_some() {
191 let threads = &mut *POOL.threads.get();
192 while started < want {
193 let k = started;
194 match thread_spawn(THR_STACK, Box::new(move || worker(k))) {
195 Some(t) => threads[k] = Some(t),
196 None => break,
197 }
198 started += 1;
199 }
200 }
201 }
202 POOL.n.store(started as u32, SeqCst);
203 POOL.state.swap(TS_READY, SeqCst);
204 started as u32
205}
206
207pub fn thr_count() -> u32 {
209 if POOL.state.load(SeqCst) == TS_READY { POOL.n.load(SeqCst) } else { thr_init(0) }
210}
211
212pub fn thr_shutdown() {
214 loop {
217 match POOL.state.compare_exchange(TS_READY, TS_STOP, SeqCst, SeqCst) {
218 Ok(_) => break,
219 Err(TS_NONE) => return,
220 Err(_) => thread_yield(), }
222 }
223 POOL.quit.store(1, SeqCst);
224 let n = POOL.n.load(SeqCst);
225 if let Some(s) = work_sem() {
226 s.post(n);
227 }
228 unsafe {
231 let threads = &mut *POOL.threads.get();
232 for t in threads.iter_mut().take(n as usize) {
233 if let Some(t) = t.take() {
234 t.join();
235 }
236 }
237 *POOL.work.get() = None;
238 *POOL.donesem.get() = None;
239 }
240 POOL.n.store(0, SeqCst);
241 POOL.state.store(TS_NONE, SeqCst);
242}
243
244fn q_lock() {
247 loop {
248 if POOL.lock.swap(1, SeqCst) == 0 {
249 return;
250 }
251 let mut spin = SPIN_LOCK;
252 loop {
253 core::hint::spin_loop();
254 if POOL.lock.load(SeqCst) == 0 {
255 break;
256 }
257 spin -= 1;
258 if spin == 0 {
259 thread_yield();
260 break;
261 }
262 }
263 }
264}
265
266fn q_unlock() {
267 POOL.lock.store(0, SeqCst);
268}
269
270unsafe fn q_push_head(j: *const JobCtl) {
273 unsafe {
274 *(*j).link.get() = POOL.head.load(SeqCst);
275 POOL.head.store(j as *mut JobCtl, SeqCst);
276 if POOL.tail.load(SeqCst).is_null() {
277 POOL.tail.store(j as *mut JobCtl, SeqCst);
278 }
279 *(*j).flags.get() |= JF_QUEUED;
280 }
281}
282
283unsafe fn q_push_tail(j: *const JobCtl) {
284 unsafe {
285 *(*j).link.get() = core::ptr::null();
286 let t = POOL.tail.load(SeqCst);
287 if t.is_null() {
288 POOL.head.store(j as *mut JobCtl, SeqCst);
289 } else {
290 *(*t).link.get() = j;
291 }
292 POOL.tail.store(j as *mut JobCtl, SeqCst);
293 *(*j).flags.get() |= JF_QUEUED;
294 }
295}
296
297unsafe fn q_unlink(j: *const JobCtl) {
298 unsafe {
299 let mut prev: *const JobCtl = core::ptr::null();
300 let mut cur = POOL.head.load(SeqCst) as *const JobCtl;
301 while !cur.is_null() {
302 if cur == j {
303 let next = *(*j).link.get();
304 if prev.is_null() {
305 POOL.head.store(next as *mut JobCtl, SeqCst);
306 } else {
307 *(*prev).link.get() = next;
308 }
309 if POOL.tail.load(SeqCst) as *const JobCtl == j {
310 POOL.tail.store(prev as *mut JobCtl, SeqCst);
311 }
312 *(*j).flags.get() &= !JF_QUEUED;
313 return;
314 }
315 prev = cur;
316 cur = *(*cur).link.get();
317 }
318 }
319}
320
321fn pick() -> *const JobCtl {
323 q_lock();
324 let h = POOL.head.load(SeqCst) as *const JobCtl;
325 if !h.is_null() {
326 unsafe { *(*h).active.get() += 1 };
328 }
329 q_unlock();
330 h
331}
332
333fn run_items(j: &JobCtl) {
335 let f = unsafe { &**j.f.get() };
337 let count = j.count();
338 while j.cancel.load(SeqCst) == 0 {
339 let i = j.next.fetch_add(1, SeqCst);
340 if i >= count {
341 break;
342 }
343 f(i as usize, j);
344 j.done.fetch_add(1, SeqCst);
345 }
346}
347
348fn leave(j: *const JobCtl) {
351 q_lock();
352 let fin = unsafe {
354 let j = &*j;
355 if *j.flags.get() & JF_QUEUED != 0
356 && (j.cancel.load(SeqCst) != 0 || j.next.load(SeqCst) >= j.count())
357 {
358 q_unlink(j); }
360 *j.active.get() -= 1;
361 *j.active.get() == 0 && *j.flags.get() & JF_QUEUED == 0
362 };
363 q_unlock();
364 if fin {
365 finish(j);
366 }
367}
368
369fn finish(j: *const JobCtl) {
372 unsafe {
374 let flags = *(*j).flags.get();
375 (*j).state.swap(JS_DONE, SeqCst);
376 finish_rest(flags);
378 }
379}
380
381fn finish_rest(flags: u32) {
382 if flags & JF_ASYNC != 0 {
383 wake();
384 }
385 let d = POOL.dwait.swap(0, SeqCst);
386 if d > 0 {
387 if let Some(s) = done_sem() {
388 s.post(d as u32);
389 }
390 }
391}
392
393fn wait_done(j: &JobCtl) {
395 for _ in 0..SPIN_WAIT {
396 if j.state.load(SeqCst) == JS_DONE {
397 return;
398 }
399 core::hint::spin_loop();
400 }
401 loop {
402 POOL.dwait.fetch_add(1, SeqCst);
404 if j.state.load(SeqCst) == JS_DONE {
405 return;
406 }
407 match done_sem() {
408 Some(s) => {
409 if !s.wait(WAIT_POLL_MS) {
410 let mut v = POOL.dwait.load(SeqCst);
412 while v > 0 {
413 match POOL.dwait.compare_exchange(v, v - 1, SeqCst, SeqCst) {
414 Ok(_) => break,
415 Err(x) => v = x,
416 }
417 }
418 }
419 }
420 None => thread_yield(),
421 }
422 if j.state.load(SeqCst) == JS_DONE {
423 return;
424 }
425 }
426}
427
428fn worker(k: usize) {
429 let top = 0u8;
430 POOL.stk[k].store(core::hint::black_box(&top) as *const u8 as usize, SeqCst);
431 'outer: loop {
432 let j = pick();
433 if !j.is_null() {
434 let j = unsafe { &*j };
436 run_items(j);
437 leave(j);
438 continue;
439 }
440 if POOL.quit.load(SeqCst) != 0 {
441 break;
442 }
443 for _ in 0..SPIN_IDLE {
444 core::hint::spin_loop();
445 if !POOL.head.load(SeqCst).is_null() {
446 continue 'outer;
447 }
448 }
449 if let Some(s) = work_sem() {
450 s.wait(-1);
451 }
452 }
453 POOL.stk[k].store(0, SeqCst);
454}
455
456pub fn parallel_for(count: usize, f: &(dyn Fn(usize, &JobCtl) + Sync)) -> Result<(), Cancelled> {
460 if count == 0 {
461 return Ok(());
462 }
463 let scopes = crate::policy::scopes_here();
465 if !scopes.is_empty() {
466 let s = &scopes;
467 return loop_items(count, &|i, j| crate::policy::in_scopes(s, || f(i, j)));
468 }
469 loop_items(count, f)
470}
471
472fn loop_items(count: usize, f: &(dyn Fn(usize, &JobCtl) + Sync)) -> Result<(), Cancelled> {
473 let fp: *const ItemFn = unsafe { core::mem::transmute::<&(dyn Fn(usize, &JobCtl) + Sync), *const ItemFn>(f) };
476 let job = JobCtl::new(fp, count as u64);
477 job.state.store(JS_RUNNING, SeqCst);
478 unsafe { *job.active.get() = 1 }; let n = thr_count();
481 if n == 0 || count <= 1 {
482 run_items(&job);
483 job.state.store(JS_DONE, SeqCst);
484 } else {
485 q_lock();
486 unsafe { q_push_head(&job) }; q_unlock();
489 if let Some(s) = work_sem() {
490 s.post((count - 1).min(n as usize) as u32);
491 }
492 run_items(&job);
493 leave(&job);
494 wait_done(&job);
495 }
496 job.result()
497}
498
499fn job_cancel(j: &JobCtl) {
502 j.cancel.swap(1, SeqCst);
503 if j.state.load(SeqCst) != JS_RUNNING {
504 return;
505 }
506 q_lock();
507 let fin = unsafe {
509 if *j.flags.get() & JF_QUEUED != 0 && *j.active.get() == 0 {
510 q_unlink(j);
511 true
512 } else {
513 false
514 }
515 };
516 q_unlock();
517 if fin {
518 finish(j);
519 }
520}
521
522pub struct Job {
524 rec: Box<JobCtl>,
525 f: Option<Box<dyn Fn(usize, &JobCtl) + Send + Sync>>,
526}
527
528impl Default for Job {
529 fn default() -> Self {
530 Self::new()
531 }
532}
533
534impl Job {
535 pub fn new() -> Job {
536 Job { rec: Box::new(JobCtl::new(core::ptr::null::<fn(usize, &JobCtl)>() as *const ItemFn, 0)), f: None }
537 }
538
539 fn running(&self) -> bool {
540 self.rec.state.load(SeqCst) == JS_RUNNING
541 }
542
543 pub fn set(&mut self, count: u64, f: impl Fn(usize, &JobCtl) + Send + Sync + 'static) -> bool {
545 if self.running() {
546 return false;
547 }
548 let b: Box<dyn Fn(usize, &JobCtl) + Send + Sync> = Box::new(f);
549 unsafe {
551 *self.rec.f.get() = &*b as &(dyn Fn(usize, &JobCtl) + Sync) as *const ItemFn;
552 *self.rec.count.get() = count;
553 }
554 self.f = Some(b);
555 true
556 }
557
558 pub fn set_count(&mut self, count: u64) -> bool {
560 if self.running() {
561 return false;
562 }
563 unsafe { *self.rec.count.get() = count };
565 true
566 }
567
568 pub fn start(&self) -> bool {
570 let j: &JobCtl = &self.rec;
571 let mut s = j.state.load(SeqCst);
574 loop {
575 if s == JS_RUNNING || s == JS_STARTING {
576 return false;
577 }
578 match j.state.compare_exchange(s, JS_STARTING, SeqCst, SeqCst) {
579 Ok(_) => break,
580 Err(x) => s = x,
581 }
582 }
583 let n = thr_count();
584 let empty = j.count() == 0 || self.f.is_none();
585 let here = !empty && n == 0; j.next.store(0, SeqCst);
587 j.done.store(0, SeqCst);
588 j.cancel.store(0, SeqCst);
589 unsafe {
592 *j.link.get() = core::ptr::null();
593 *j.active.get() = here as u32;
594 *j.flags.get() = JF_ASYNC;
595 }
596 j.state.store(JS_RUNNING, SeqCst);
597 if empty {
598 finish(j);
599 return true;
600 }
601 if here {
602 run_items(j);
603 finish(j);
604 return true;
605 }
606 q_lock();
607 unsafe { q_push_tail(j) };
609 q_unlock();
610 if let Some(s) = work_sem() {
611 s.post(j.count().min(n as u64) as u32);
612 }
613 true
614 }
615
616 pub fn wait(&self) -> Result<(), Cancelled> {
618 let j: &JobCtl = &self.rec;
619 if self.running() {
620 q_lock();
621 let help = unsafe {
623 if *j.flags.get() & JF_QUEUED != 0 {
624 *j.active.get() += 1;
625 true
626 } else {
627 false
628 }
629 };
630 q_unlock();
631 if help {
632 run_items(j);
633 leave(j);
634 }
635 wait_done(j);
636 }
637 j.result()
638 }
639
640 pub fn cancel(&self) {
642 job_cancel(&self.rec)
643 }
644
645 pub fn done(&self) -> bool {
647 !self.running()
648 }
649
650 pub fn items_done(&self) -> u64 {
651 self.rec.items_done()
652 }
653
654 pub fn count(&self) -> u64 {
655 self.rec.count()
656 }
657}
658
659impl Drop for Job {
660 fn drop(&mut self) {
661 if self.running() {
662 self.cancel();
663 let _ = self.wait();
664 }
665 }
666}
667
668pub fn thr_self() -> usize {
670 let here = 0u8;
671 let sp = core::hint::black_box(&here) as *const u8 as usize;
672 let n = (POOL.n.load(SeqCst) as usize).min(THR_MAX);
673 for k in 0..n {
674 let top = POOL.stk[k].load(SeqCst);
675 if top != 0 && sp <= top && sp > top.wrapping_sub(THR_STACK - 65536) {
676 return k;
677 }
678 }
679 n
680}