Index: arch/amd64/amd64/cpu.c =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/cpu.c,v retrieving revision 1.102 diff -u -p -r1.102 cpu.c --- arch/amd64/amd64/cpu.c 28 Jul 2016 21:57:57 -0000 1.102 +++ arch/amd64/amd64/cpu.c 12 Mar 2017 11:38:31 -0000 @@ -426,6 +426,7 @@ cpu_attach(struct device *parent, struct /* * Enable local apic */ + lapic_attach(ci); lapic_enable(); lapic_calibrate_timer(ci); #endif @@ -462,6 +463,9 @@ cpu_attach(struct device *parent, struct cpu_vm_init(ci); #if defined(MULTIPROCESSOR) + mtx_init(&ci->ci_xcall_mtx, IPL_HIGH); + TAILQ_INIT(&ci->ci_xcall_list); + if (mp_verbose) { printf("%s: kstack at 0x%lx for %d bytes\n", sc->sc_dev.dv_xname, kstack, USPACE); @@ -683,6 +687,7 @@ cpu_hatch(void *v) ci->ci_flags |= CPUF_PRESENT; + lapic_attach(ci); lapic_enable(); lapic_startclock(); Index: arch/amd64/amd64/intr.c =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/intr.c,v retrieving revision 1.48 diff -u -p -r1.48 intr.c --- arch/amd64/amd64/intr.c 22 Jun 2016 01:12:38 -0000 1.48 +++ arch/amd64/amd64/intr.c 12 Mar 2017 11:38:31 -0000 @@ -550,7 +550,10 @@ struct intrhand fake_softclock_intrhand; struct intrhand fake_softnet_intrhand; struct intrhand fake_softtty_intrhand; struct intrhand fake_timer_intrhand; +#ifdef MULTIPROCESSOR struct intrhand fake_ipi_intrhand; +struct intrhand fake_xcall_intrhand; +#endif #if NXEN > 0 struct intrhand fake_xen_intrhand; #endif @@ -621,6 +624,15 @@ cpu_intr_init(struct cpu_info *ci) isp->is_handlers = &fake_ipi_intrhand; isp->is_pic = &local_pic; ci->ci_isources[LIR_IPI] = isp; + isp = malloc(sizeof (struct intrsource), M_DEVBUF, M_NOWAIT|M_ZERO); + if (isp == NULL) + panic("can't allocate fixed interrupt source"); + isp->is_recurse = Xxcallintr; + isp->is_resume = Xxcallintr; + fake_xcall_intrhand.ih_level = IPL_SOFTCLOCK; + isp->is_handlers = &fake_xcall_intrhand; + isp->is_pic = &local_pic; + ci->ci_isources[SIR_XCALL] = isp; #endif #if NXEN > 0 isp = malloc(sizeof (struct intrsource), M_DEVBUF, M_NOWAIT|M_ZERO); @@ -741,6 +753,5 @@ softintr(int sir) { struct cpu_info *ci = curcpu(); - __asm volatile("lock; orq %1, %0" : - "=m"(ci->ci_ipending) : "ir" (1UL << sir)); + x86_atomic_setbits_u64(&ci->ci_ipending, 1UL << sir); } Index: arch/amd64/amd64/ipifuncs.c =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/ipifuncs.c,v retrieving revision 1.28 diff -u -p -r1.28 ipifuncs.c --- arch/amd64/amd64/ipifuncs.c 23 Nov 2015 22:57:12 -0000 1.28 +++ arch/amd64/amd64/ipifuncs.c 12 Mar 2017 11:38:31 -0000 @@ -65,6 +65,8 @@ void x86_64_ipi_halt(struct cpu_info *); void x86_64_ipi_synch_fpu(struct cpu_info *); void x86_64_ipi_flush_fpu(struct cpu_info *); +void x86_64_ipi_xcall(struct cpu_info *); + #if NVMM > 0 void x86_64_ipi_start_vmm(struct cpu_info *); void x86_64_ipi_stop_vmm(struct cpu_info *); @@ -102,6 +104,7 @@ void (*ipifunc[X86_NIPI])(struct cpu_inf NULL, NULL, #endif + x86_64_ipi_xcall, }; void @@ -163,3 +166,13 @@ x86_64_ipi_stop_vmm(struct cpu_info *ci) stop_vmm_on_cpu(ci); } #endif /* NVMM > 0 */ + +void +x86_64_ipi_xcall(struct cpu_info *ci) +{ + /* + * this is an inlining of softintr() because we already have + * curcpu() and the SIR_XCALL bit to set. + */ + x86_atomic_setbits_u64(&ci->ci_ipending, 1UL << SIR_XCALL); +}; Index: arch/amd64/amd64/lapic.c =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/lapic.c,v retrieving revision 1.45 diff -u -p -r1.45 lapic.c --- arch/amd64/amd64/lapic.c 1 Nov 2016 01:13:19 -0000 1.45 +++ arch/amd64/amd64/lapic.c 12 Mar 2017 11:38:31 -0000 @@ -35,6 +35,9 @@ #include #include #include +#include +#include +#include #include @@ -62,13 +65,43 @@ #include #endif -struct evcount clk_count; #ifdef MULTIPROCESSOR struct evcount ipi_count; #endif +struct lapic { + char lapic_clk_name[16]; + struct evcount lapic_clk_count; + + struct task_heap lapic_tasks; + int lapic_now; + int lapic_state; +#define LAPIC_S_IDLE 0 +#define LAPIC_S_RUNNING 1 + + struct task lapic_hardclock; + struct task lapic_statclock; + struct intrframe *lapic_frame; + + struct task lapic_tmo_wait; /* waits in lapic_tasks */ + struct task lapic_tmo_fire; /* runs in ci_xcall_list */ + struct mutex lapic_tmo_mtx; /* protects tmo_tasks */ + struct task_heap lapic_tmo_tasks; +}; + +int lapic_add(struct lapic *, struct task *, int); +void lapic_run(struct lapic *, int); + +void lapic_hardclock(void *); +void lapic_statclock(void *); + +void lapic_tmo_wait(void *); +void lapic_tmo_fire(void *); + +int lapic_tmo_add_usec(struct cpu_info *, struct task *, int); +int lapic_tmo_del(struct cpu_info *, struct task *); + void lapic_delay(int); -static u_int32_t lapic_gettick(void); void lapic_clockintr(void *, struct intrframe); void lapic_initclocks(void); void lapic_map(paddr_t); @@ -223,10 +256,37 @@ lapic_map(paddr_t lapic_base) enable_intr(); } +void +lapic_attach(struct cpu_info *ci) +{ + static u_int64_t clk_irq = 0; + struct lapic *l; + + l = malloc(sizeof(*l), M_DEVBUF, M_WAITOK); + + snprintf(l->lapic_clk_name, sizeof(l->lapic_clk_name), + "cpu%uclk", CPU_INFO_UNIT(ci)); + evcount_attach(&l->lapic_clk_count, l->lapic_clk_name, &clk_irq); + + HEAP_INIT(task_heap, &l->lapic_tasks); + l->lapic_now = 0; + l->lapic_state = LAPIC_S_IDLE; + + task_set(&l->lapic_hardclock, lapic_hardclock, l); + task_set(&l->lapic_statclock, lapic_statclock, l); + + task_set(&l->lapic_tmo_wait, lapic_tmo_wait, ci); + task_set(&l->lapic_tmo_fire, lapic_tmo_fire, l); + mtx_init(&l->lapic_tmo_mtx, IPL_HIGH); + HEAP_INIT(task_heap, &l->lapic_tmo_tasks); + + ci->ci_lapic = l; +} /* * enable local apic */ + void lapic_enable(void) { @@ -330,7 +390,6 @@ lapic_set_lvt(void) void lapic_boot_init(paddr_t lapic_base) { - static u_int64_t clk_irq = 0; #ifdef MULTIPROCESSOR static u_int64_t ipi_irq = 0; #endif @@ -364,13 +423,12 @@ lapic_boot_init(paddr_t lapic_base) idt_vec_set(LAPIC_HYPERV_VECTOR, Xintr_hyperv_upcall); #endif - evcount_attach(&clk_count, "clock", &clk_irq); #ifdef MULTIPROCESSOR evcount_attach(&ipi_count, "ipi", &ipi_irq); #endif } -static __inline u_int32_t +static inline u_int32_t lapic_gettick(void) { return lapic_readreg(LAPIC_CCR_TIMER); @@ -378,8 +436,6 @@ lapic_gettick(void) #include /* for hz */ -u_int32_t lapic_tval; - /* * this gets us up to a 4GHz busclock.... */ @@ -388,34 +444,256 @@ u_int32_t lapic_frac_usec_per_cycle; u_int64_t lapic_frac_cycle_per_usec; u_int32_t lapic_delaytab[26]; +unsigned int lapic_misses; + void lapic_clockintr(void *arg, struct intrframe frame) { struct cpu_info *ci = curcpu(); + struct lapic *l = ci->ci_lapic; + struct task *t, key; int floor; + int now; + + l->lapic_state = LAPIC_S_IDLE; + l->lapic_frame = &frame; + now = l->lapic_now + lapic_readreg(LAPIC_ICR_TIMER); floor = ci->ci_handled_intr_level; ci->ci_handled_intr_level = ci->ci_ilevel; - hardclock((struct clockframe *)&frame); + + key.t_deadline = now; + + while ((t = HEAP_CEXTRACT(task_heap, &l->lapic_tasks, &key)) != NULL) { + CLR(t->t_flags, TASK_ONQUEUE); + (*t->t_func)(t->t_arg); + } + ci->ci_handled_intr_level = floor; - clk_count.ec_count++; + if (l->lapic_state != LAPIC_S_RUNNING) + lapic_run(l, now); + + ci->ci_lapic->lapic_clk_count.ec_count++; +} + +static inline int64_t +lapic_usec(int usec) +{ + if (usec <= 25) + return (lapic_delaytab[usec]); + + return ((lapic_frac_cycle_per_usec * usec) >> 32); +} + +void +lapic_run(struct lapic *l, int now) +{ + struct task *t; + int diff; + + t = HEAP_FIRST(task_heap, &l->lapic_tasks); + diff = t->t_deadline - now; + if (diff < 1) + diff = 1; + + l->lapic_now = now; + l->lapic_state = LAPIC_S_RUNNING; + lapic_writereg(LAPIC_LVTT, LAPIC_TIMER_VECTOR); + lapic_writereg(LAPIC_ICR_TIMER, diff); +} + +int +lapic_add(struct lapic *l, struct task *t, int usec) +{ + int rv = 1; + int now; + + lapic_writereg(LAPIC_LVTT, LAPIC_LVTT_M | LAPIC_TIMER_VECTOR); + now = l->lapic_now; + now += lapic_readreg(LAPIC_ICR_TIMER) - lapic_readreg(LAPIC_CCR_TIMER); + lapic_writereg(LAPIC_ICR_TIMER, 0); + + if (ISSET(t->t_flags, TASK_ONQUEUE)) { + HEAP_REMOVE(task_heap, &l->lapic_tasks, t); + rv = 0; + } else + SET(t->t_flags, TASK_ONQUEUE); + + t->t_deadline = now + lapic_usec(usec); + HEAP_INSERT(task_heap, &l->lapic_tasks, t); + + lapic_run(l, now); + + return (rv); +} + +void +lapic_hardclock(void *arg) +{ + struct lapic *l = arg; + + hardclock(l->lapic_frame); + + lapic_add(l, &l->lapic_hardclock, 1000000 / hz); +} + +void +lapic_statclock(void *arg) +{ + struct lapic *l = arg; + + statclock(l->lapic_frame); + + lapic_add(l, &l->lapic_statclock, 1000000 / stathz); +} + +void +lapic_tmo_wait(void *arg) +{ + struct cpu_info *ci = arg; + struct lapic *l = ci->ci_lapic; + struct task *t = &l->lapic_tmo_fire; + + if (ISSET(t->t_flags, TASK_ONQUEUE)) + return; + + mtx_enter(&ci->ci_xcall_mtx); + if (!ISSET(t->t_flags, TASK_ONQUEUE)) { + TAILQ_INSERT_TAIL(&ci->ci_xcall_list, t, t_entry); + SET(t->t_flags, TASK_ONQUEUE); + + x86_atomic_setbits_u64(&ci->ci_ipending, 1UL << SIR_XCALL); + } + mtx_leave(&ci->ci_xcall_mtx); +} + +void +lapic_tmo_fire(void *arg) +{ + struct lapic *l = arg; + struct task *t; + struct task work; + + mtx_enter(&l->lapic_tmo_mtx); + while ((t = HEAP_CEXTRACT(task_heap, &l->lapic_tmo_tasks, + &l->lapic_tmo_wait)) != NULL) { + CLR(t->t_flags, TASK_ONQUEUE); + work = *t; + mtx_leave(&l->lapic_tmo_mtx); + + (*work.t_func)(work.t_arg); + + if (HEAP_EMPTY(task_heap, &l->lapic_tmo_tasks)) + return; /* short circuit */ + + mtx_enter(&l->lapic_tmo_mtx); + } + mtx_leave(&l->lapic_tmo_mtx); +} + +struct lapic_tmo_proxy { + struct task *t; + int usecs; + int rv; + volatile int spin; +}; + +void +_lapic_tmo_add(void *arg) +{ + struct lapic_tmo_proxy *proxy = arg; + struct task *t = proxy->t; + struct lapic *l = curcpu()->ci_lapic; + struct task *wait = &l->lapic_tmo_wait; + int now; + + mtx_enter(&l->lapic_tmo_mtx); + lapic_writereg(LAPIC_LVTT, LAPIC_LVTT_M | LAPIC_TIMER_VECTOR); + now = l->lapic_now; + now += lapic_readreg(LAPIC_ICR_TIMER) - lapic_readreg(LAPIC_CCR_TIMER); + lapic_writereg(LAPIC_ICR_TIMER, 0); + + if (ISSET(t->t_flags, TASK_ONQUEUE)) { + HEAP_REMOVE(task_heap, &l->lapic_tmo_tasks, t); + proxy->rv = 0; + } else { + SET(t->t_flags, TASK_ONQUEUE); + proxy->rv = 1; + } + + t->t_deadline = now + lapic_usec(proxy->usecs); + HEAP_INSERT(task_heap, &l->lapic_tmo_tasks, t); + + /* get the deadline for the hardclock wait task */ + t = HEAP_FIRST(task_heap, &l->lapic_tmo_tasks); + + if (ISSET(wait->t_flags, TASK_ONQUEUE)) + HEAP_REMOVE(task_heap, &l->lapic_tasks, wait); + else + SET(wait->t_flags, TASK_ONQUEUE); + + wait->t_deadline = t->t_deadline; + HEAP_INSERT(task_heap, &l->lapic_tasks, wait); + + lapic_run(l, now); + mtx_leave(&l->lapic_tmo_mtx); + + proxy->spin = 0; /* release the other cpu */ +} + +int +lapic_tmo_add(struct cpu_info *ci, struct task *t, int usecs) +{ + struct lapic_tmo_proxy proxy = { .t = t, .usecs = usecs, .spin = 1 }; + struct task xc = TASK_INITIALIZER(_lapic_tmo_add, &proxy); + + cpu_xcall(ci, &xc); + + while (proxy.spin) + __asm volatile("pause": : :"memory"); + + return (proxy.rv); +} + +int +lapic_tmo_del(struct cpu_info *ci, struct task *t) +{ + struct lapic *l = ci->ci_lapic; + int rv = 0; + + /* + * reach over to the target cpu and remove the task directly. this + * doesnt remove or reschedule the hardclock wait task, it just lets + * it happen and have no effect. + */ + + if (!ISSET(t->t_flags, TASK_ONQUEUE)) + return (0); + + mtx_enter(&l->lapic_tmo_mtx); + if (ISSET(t->t_flags, TASK_ONQUEUE)) { + HEAP_REMOVE(task_heap, &l->lapic_tmo_tasks, t); + CLR(t->t_flags, TASK_ONQUEUE); + rv = 1; + } + mtx_leave(&l->lapic_tmo_mtx); + + return (rv); } void lapic_startclock(void) { + struct cpu_info *ci = curcpu(); + struct lapic *l = ci->ci_lapic; + /* - * Start local apic countdown timer running, in repeated mode. - * - * Mask the clock interrupt and set mode, - * then set divisor, - * then unmask and set the vector. + * Start local apic countdown timer running; */ - lapic_writereg(LAPIC_LVTT, LAPIC_LVTT_TM|LAPIC_LVTT_M); lapic_writereg(LAPIC_DCR_TIMER, LAPIC_DCRT_DIV1); - lapic_writereg(LAPIC_ICR_TIMER, lapic_tval); - lapic_writereg(LAPIC_LVTT, LAPIC_LVTT_TM|LAPIC_TIMER_VECTOR); + lapic_add(l, &l->lapic_hardclock, 1000000 / hz); + lapic_add(l, &l->lapic_statclock, 1000000 / stathz); } void @@ -503,17 +781,7 @@ lapic_calibrate_timer(struct cpu_info *c ci->ci_dev->dv_xname, tmp / (1000 * 1000)); if (lapic_per_second != 0) { - /* - * reprogram the apic timer to run in periodic mode. - * XXX need to program timer on other cpu's, too. - */ - lapic_tval = (lapic_per_second * 2) / hz; - lapic_tval = (lapic_tval / 2) + (lapic_tval & 0x1); - - lapic_writereg(LAPIC_LVTT, LAPIC_LVTT_TM | LAPIC_LVTT_M | - LAPIC_TIMER_VECTOR); - lapic_writereg(LAPIC_DCR_TIMER, LAPIC_DCRT_DIV1); - lapic_writereg(LAPIC_ICR_TIMER, lapic_tval); + stathz = 128; /* * Compute fixed-point ratios between cycles and @@ -535,11 +803,13 @@ lapic_calibrate_timer(struct cpu_info *c lapic_delaytab[i] = (lapic_frac_cycle_per_usec * i) >> 32; + lapic_startclock(); + /* * Now that the timer's calibrated, use the apic timer routines * for all our timing needs.. */ - delay_func = lapic_delay; + // delay_func = lapic_delay; initclock_func = lapic_initclocks; } } @@ -551,28 +821,32 @@ lapic_calibrate_timer(struct cpu_info *c void lapic_delay(int usec) { - int32_t tick, otick; - int64_t deltat; /* XXX may want to be 64bit */ - - otick = lapic_gettick(); + struct lapic *l = curcpu()->ci_lapic; + int tick, otick; + int now, onow; + int64_t deltat; if (usec <= 0) return; - if (usec <= 25) - deltat = lapic_delaytab[usec]; - else - deltat = (lapic_frac_cycle_per_usec * usec) >> 32; - while (deltat > 0) { + deltat = lapic_usec(usec); + + onow = l->lapic_now; + otick = lapic_gettick(); + + do { + now = l->lapic_now; tick = lapic_gettick(); - if (tick > otick) - deltat -= lapic_tval - (tick - otick); - else + + if (now != onow) { + /* this is a new epoch, skip calculating a diff */ + onow = now; + } else deltat -= otick - tick; otick = tick; - - x86_pause(); - } + + __asm volatile("pause": : :"memory"); + } while (deltat > 0); } /* Index: arch/amd64/amd64/softintr.c =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/softintr.c,v retrieving revision 1.9 diff -u -p -r1.9 softintr.c --- arch/amd64/amd64/softintr.c 28 Aug 2015 00:03:53 -0000 1.9 +++ arch/amd64/amd64/softintr.c 12 Mar 2017 11:38:31 -0000 @@ -168,3 +168,49 @@ softintr_disestablish(void *arg) free(sih, M_DEVBUF, sizeof(*sih)); } + +#ifdef MULTIPROCESSOR +#include + +void +cpu_xcall(struct cpu_info *ci, struct task *t) +{ + if (ci == curcpu()) { + /* execute the task immediately on the local cpu */ + int s = splsoftclock(); + (*t->t_func)(t->t_arg); + splx(s); + } else { + mtx_enter(&ci->ci_xcall_mtx); + SET(t->t_flags, TASK_ONQUEUE); + TAILQ_INSERT_TAIL(&ci->ci_xcall_list, t, t_entry); + mtx_leave(&ci->ci_xcall_mtx); + + x86_send_ipi(ci, X86_IPI_XCALL); + } +} + +void +cpu_xcall_dispatch(void) +{ + struct cpu_info *ci = curcpu(); + struct task *t; + struct task work; + + while (!TAILQ_EMPTY(&ci->ci_xcall_list)) { + mtx_enter(&ci->ci_xcall_mtx); + t = TAILQ_FIRST(&ci->ci_xcall_list); + if (t == NULL) { + mtx_leave(&ci->ci_xcall_mtx); + break; + } + + TAILQ_REMOVE(&ci->ci_xcall_list, t, t_entry); + CLR(t->t_flags, TASK_ONQUEUE); + work = *t; + mtx_leave(&ci->ci_xcall_mtx); + + (*work.t_func)(work.t_arg); + } +} +#endif Index: arch/amd64/amd64/vector.S =================================================================== RCS file: /cvs/src/sys/arch/amd64/amd64/vector.S,v retrieving revision 1.47 diff -u -p -r1.47 vector.S --- arch/amd64/amd64/vector.S 4 Sep 2016 09:22:28 -0000 1.47 +++ arch/amd64/amd64/vector.S 12 Mar 2017 11:38:31 -0000 @@ -1108,3 +1108,11 @@ IDTVEC(softclock) call _C_LABEL(softintr_dispatch) decl CPUVAR(IDEPTH) jmp *%r13 + +IDTVEC(xcallintr) + movl $IPL_SOFTCLOCK, CPUVAR(ILEVEL) + sti + incl CPUVAR(IDEPTH) + call _C_LABEL(cpu_xcall_dispatch) + decl CPUVAR(IDEPTH) + jmp *%r13 Index: arch/amd64/include/cpu.h =================================================================== RCS file: /cvs/src/sys/arch/amd64/include/cpu.h,v retrieving revision 1.108 diff -u -p -r1.108 cpu.h --- arch/amd64/include/cpu.h 2 Mar 2017 10:38:10 -0000 1.108 +++ arch/amd64/include/cpu.h 12 Mar 2017 11:38:31 -0000 @@ -52,6 +52,9 @@ #include #include +/* for xcalls */ +#include +#include #ifdef _KERNEL /* VMXON region (Intel) */ @@ -84,6 +87,8 @@ union vmm_cpu_cap { struct svm vcc_svm; }; +struct lapic; + struct x86_64_tss; struct cpu_info { struct device *ci_dev; @@ -117,6 +122,7 @@ struct cpu_info { int ci_mutex_level; #endif + struct lapic *ci_lapic; volatile u_int ci_flags; u_int32_t ci_ipis; @@ -171,6 +177,8 @@ struct cpu_info { #ifdef MULTIPROCESSOR struct srp_hazard ci_srp_hazards[SRP_HAZARD_NUM]; + struct mutex ci_xcall_mtx; + struct task_list ci_xcall_list; #endif struct ksensordev ci_sensordev; Index: arch/amd64/include/i82489var.h =================================================================== RCS file: /cvs/src/sys/arch/amd64/include/i82489var.h,v retrieving revision 1.17 diff -u -p -r1.17 i82489var.h --- arch/amd64/include/i82489var.h 22 Jun 2016 01:12:38 -0000 1.17 +++ arch/amd64/include/i82489var.h 12 Mar 2017 11:38:31 -0000 @@ -119,6 +119,7 @@ struct cpu_info; extern void lapic_boot_init(paddr_t); extern void lapic_set_lvt(void); +extern void lapic_attach(struct cpu_info *); extern void lapic_enable(void); extern void lapic_disable(void); extern void lapic_calibrate_timer(struct cpu_info *ci); Index: arch/amd64/include/intr.h =================================================================== RCS file: /cvs/src/sys/arch/amd64/include/intr.h,v retrieving revision 1.29 diff -u -p -r1.29 intr.h --- arch/amd64/include/intr.h 13 Sep 2015 11:48:17 -0000 1.29 +++ arch/amd64/include/intr.h 12 Mar 2017 11:38:31 -0000 @@ -219,6 +219,8 @@ void x86_ipi_handler(void); void x86_setperf_ipi(struct cpu_info *); extern void (*ipifunc[X86_NIPI])(struct cpu_info *); + +extern void Xxcallintr(void); #endif #endif /* !_LOCORE */ Index: arch/amd64/include/intrdefs.h =================================================================== RCS file: /cvs/src/sys/arch/amd64/include/intrdefs.h,v retrieving revision 1.16 diff -u -p -r1.16 intrdefs.h --- arch/amd64/include/intrdefs.h 22 Jun 2016 01:12:38 -0000 1.16 +++ arch/amd64/include/intrdefs.h 12 Mar 2017 11:38:31 -0000 @@ -53,9 +53,10 @@ #define SIR_CLOCK 61 #define SIR_NET 60 #define SIR_TTY 59 +#define SIR_XCALL 58 -#define LIR_XEN 58 -#define LIR_HYPERV 57 +#define LIR_XEN 57 +#define LIR_HYPERV 56 /* * Maximum # of interrupt sources per CPU. 64 to fit in one word. @@ -83,13 +84,14 @@ #define X86_IPI_DDB 0x00000080 #define X86_IPI_START_VMM 0x00000100 #define X86_IPI_STOP_VMM 0x00000200 +#define X86_IPI_XCALL 0x00000400 -#define X86_NIPI 10 +#define X86_NIPI 11 #define X86_IPI_NAMES { "halt IPI", "nop IPI", "FPU flush IPI", \ "FPU synch IPI", "TLB shootdown IPI", \ "MTRR update IPI", "setperf IPI", "ddb IPI", \ - "VMM start IPI", "VMM stop IPI" } + "VMM start IPI", "VMM stop IPI", "xcall IPI" } #define IREENT_MAGIC 0x18041969 Index: arch/amd64/include/specialreg.h =================================================================== RCS file: /cvs/src/sys/arch/amd64/include/specialreg.h,v retrieving revision 1.54 diff -u -p -r1.54 specialreg.h --- arch/amd64/include/specialreg.h 24 Jan 2017 09:02:33 -0000 1.54 +++ arch/amd64/include/specialreg.h 12 Mar 2017 11:38:31 -0000 @@ -414,6 +414,7 @@ #define MSR_MC3_STATUS 0x411 #define MSR_MC3_ADDR 0x412 #define MSR_MC3_MISC 0x413 +#define MSR_TSC_DEADLINE 0x6E0 /* VIA MSR */ #define MSR_CENT_TMTEMPERATURE 0x1423 /* Thermal monitor temperature */ Index: kern/init_main.c =================================================================== RCS file: /cvs/src/sys/kern/init_main.c,v retrieving revision 1.266 diff -u -p -r1.266 init_main.c --- kern/init_main.c 12 Feb 2017 04:55:08 -0000 1.266 +++ kern/init_main.c 12 Mar 2017 11:38:31 -0000 @@ -297,6 +297,7 @@ main(void *framep) /* Init timeouts. */ timeout_set(&p->p_sleep_to, endtsleep, p); + task_set(&p->p_sleep_t, endtsleep, p); /* Initialize signal state for process 0. */ signal_init(); Index: kern/kern_event.c =================================================================== RCS file: /cvs/src/sys/kern/kern_event.c,v retrieving revision 1.78 diff -u -p -r1.78 kern_event.c --- kern/kern_event.c 11 Feb 2017 19:51:06 -0000 1.78 +++ kern/kern_event.c 12 Mar 2017 11:38:31 -0000 @@ -320,25 +320,59 @@ filt_proc(struct knote *kn, long hint) return (kn->kn_fflags != 0); } +struct kq_timeout { + struct timeout kq_tmo; + struct task kq_t; + struct refcnt kq_refs; + struct cpu_info *kq_ci; +}; + +int lapic_tmo_add(struct cpu_info *, struct task *, int); +int lapic_tmo_del(struct cpu_info *, struct task *); +int kqlapic; + static void filt_timer_timeout_add(struct knote *kn) { - struct timeval tv; - int tticks; + struct kq_timeout *kqtmo = kn->kn_hook; + int rv; + + refcnt_take(&kqtmo->kq_refs); + + if (kn->kn_sdata < 133) { + kqlapic++; + rv = lapic_tmo_add(kqtmo->kq_ci, &kqtmo->kq_t, + kn->kn_sdata * 1000); + } else { + struct timeval tv; + int tticks; + + tv.tv_sec = kn->kn_sdata / 1000; + tv.tv_usec = (kn->kn_sdata % 1000) * 1000; + tticks = tvtohz(&tv); - tv.tv_sec = kn->kn_sdata / 1000; - tv.tv_usec = (kn->kn_sdata % 1000) * 1000; - tticks = tvtohz(&tv); - timeout_add(kn->kn_hook, tticks ? tticks : 1); + rv = timeout_add(kn->kn_hook, tticks ? tticks : 1); + } + + if (rv == 0) + refcnt_rele(&kqtmo->kq_refs); } void filt_timerexpire(void *knx) { struct knote *kn = knx; + struct kq_timeout *kqtmo = kn->kn_hook; + KERNEL_LOCK(); kn->kn_data++; KNOTE_ACTIVATE(kn); + KERNEL_UNLOCK(); + + if (refcnt_rele_wake(&kqtmo->kq_refs)) { + /* timerdetach is waiting */ + return; + } if ((kn->kn_flags & EV_ONESHOT) == 0) filt_timer_timeout_add(kn); @@ -351,16 +385,22 @@ filt_timerexpire(void *knx) int filt_timerattach(struct knote *kn) { - struct timeout *to; + struct kq_timeout *kqtmo; if (kq_ntimeouts > kq_timeoutmax) return (ENOMEM); kq_ntimeouts++; kn->kn_flags |= EV_CLEAR; /* automatically set */ - to = malloc(sizeof(*to), M_KEVENT, M_WAITOK); - timeout_set(to, filt_timerexpire, kn); - kn->kn_hook = to; + kqtmo = malloc(sizeof(*kqtmo), M_KEVENT, M_WAITOK); + + refcnt_init(&kqtmo->kq_refs); + timeout_set(&kqtmo->kq_tmo, filt_timerexpire, kn); + task_set(&kqtmo->kq_t, filt_timerexpire, kn); + + kqtmo->kq_ci = curcpu(); + + kn->kn_hook = kqtmo; filt_timer_timeout_add(kn); return (0); @@ -369,11 +409,17 @@ filt_timerattach(struct knote *kn) void filt_timerdetach(struct knote *kn) { - struct timeout *to; + struct kq_timeout *kqtmo = kn->kn_hook; + + if (lapic_tmo_del(kqtmo->kq_ci, &kqtmo->kq_t)) + refcnt_rele(&kqtmo->kq_refs); + if (timeout_del(&kqtmo->kq_tmo)) + refcnt_rele(&kqtmo->kq_refs); + + refcnt_finalize(&kqtmo->kq_refs, "kqtmrm"); + + free(kqtmo, M_KEVENT, sizeof(*kqtmo)); - to = (struct timeout *)kn->kn_hook; - timeout_del(to); - free(to, M_KEVENT, sizeof(*to)); kq_ntimeouts--; } @@ -703,15 +749,11 @@ kqueue_scan(struct kqueue *kq, int maxev timeout = -1; goto start; } - if (itimerfix(&atv)) { - error = EINVAL; - goto done; - } - timeout = atv.tv_sec > 24 * 60 * 60 ? - 24 * 60 * 60 * hz : tvtohz(&atv); + timeout = atv.tv_sec >= (INT_MAX / 1000000) ? INT_MAX : + atv.tv_sec * 1000000 + atv.tv_usec; - getmicrouptime(&rtv); + microuptime(&rtv); timeradd(&atv, &rtv, &atv); } else { atv.tv_sec = 0; @@ -722,13 +764,13 @@ kqueue_scan(struct kqueue *kq, int maxev retry: if (atv.tv_sec || atv.tv_usec) { - getmicrouptime(&rtv); + microuptime(&rtv); if (timercmp(&rtv, &atv, >=)) goto done; ttv = atv; timersub(&ttv, &rtv, &ttv); - timeout = ttv.tv_sec > 24 * 60 * 60 ? - 24 * 60 * 60 * hz : tvtohz(&ttv); + timeout = ttv.tv_sec >= (INT_MAX / 1000000) ? INT_MAX : + ttv.tv_sec * 1000000 + ttv.tv_usec; } start: @@ -744,7 +786,7 @@ start: error = EWOULDBLOCK; } else { kq->kq_state |= KQ_SLEEP; - error = tsleep(kq, PSOCK | PCATCH, "kqread", timeout); + error = utsleep(kq, PSOCK | PCATCH, "kqread", timeout); } splx(s); if (error == 0) Index: kern/kern_fork.c =================================================================== RCS file: /cvs/src/sys/kern/kern_fork.c,v retrieving revision 1.195 diff -u -p -r1.195 kern_fork.c --- kern/kern_fork.c 12 Feb 2017 04:55:08 -0000 1.195 +++ kern/kern_fork.c 12 Mar 2017 11:38:31 -0000 @@ -164,6 +164,7 @@ thread_new(struct proc *parent, vaddr_t * Initialize the timeouts. */ timeout_set(&p->p_sleep_to, endtsleep, p); + task_set(&p->p_sleep_t, endtsleep, p); /* * set priority of child to be that of parent Index: kern/kern_synch.c =================================================================== RCS file: /cvs/src/sys/kern/kern_synch.c,v retrieving revision 1.138 diff -u -p -r1.138 kern_synch.c --- kern/kern_synch.c 31 Jan 2017 12:16:20 -0000 1.138 +++ kern/kern_synch.c 12 Mar 2017 11:38:31 -0000 @@ -50,6 +50,7 @@ #include #include #include +#include #include #include @@ -156,6 +157,64 @@ tsleep(const volatile void *ident, int p return (error); } +int usleep_finish_timeout(struct cpu_info *, struct sleep_state *); +int lapic_tmo_add(struct cpu_info *, struct task *, int); +int lapic_tmo_del(struct cpu_info *, struct task *); + +int +utsleep(const volatile void *ident, int priority, const char *wmesg, int usec) +{ + struct cpu_info *ci = curcpu(); + struct sleep_state sls; + int error, error1; +#ifdef MULTIPROCESSOR + int hold_count; +#endif + + KASSERT((priority & ~(PRIMASK | PCATCH)) == 0); + +#ifdef DDB + if (cold == 2) + db_stack_dump(); +#endif + if (cold || panicstr) { + int s; + /* + * After a panic, or during autoconfiguration, + * just give interrupts a chance, then just return; + * don't run any other procs or panic below, + * in case this is the idle process and already asleep. + */ + s = splhigh(); + splx(safepri); +#ifdef MULTIPROCESSOR + if (__mp_lock_held(&kernel_lock)) { + hold_count = __mp_release_all(&kernel_lock); + __mp_acquire_count(&kernel_lock, hold_count); + } +#endif + splx(s); + return (0); + } + + sleep_setup(&sls, ident, priority, wmesg); + if (usec > 133000) + timeout_add_usec(&curproc->p_sleep_to, usec); + else if (usec) + lapic_tmo_add(ci, &curproc->p_sleep_t, usec); + sleep_setup_signal(&sls, priority); + + sleep_finish(&sls, 1); + error1 = usleep_finish_timeout(ci, &sls); + error = sleep_finish_signal(&sls); + + /* Signal errors are higher priority than timeouts. */ + if (error == 0 && error1 != 0) + error = error1; + + return (error); +} + /* * Same as tsleep, but if we have a mutex provided, then once we've * entered the sleep queue we drop the mutex. After sleeping we re-lock. @@ -338,6 +398,22 @@ sleep_finish_timeout(struct sleep_state return (0); } +int +usleep_finish_timeout(struct cpu_info *ci, struct sleep_state *sls) +{ + struct proc *p = curproc; + + if (p->p_flag & P_TIMEOUT) { + atomic_clearbits_int(&p->p_flag, P_TIMEOUT); + return (EWOULDBLOCK); + } else { + timeout_del(&p->p_sleep_to); + lapic_tmo_del(ci, &p->p_sleep_t); + } + + return (0); +} + void sleep_setup_signal(struct sleep_state *sls, int prio) { @@ -665,11 +741,16 @@ refcnt_rele(struct refcnt *r) return (refcnt == 0); } -void +int refcnt_rele_wake(struct refcnt *r) { - if (refcnt_rele(r)) + int last; + + last = refcnt_rele(r); + if (last) wakeup_one(r); + + return (last); } void Index: kern/kern_task.c =================================================================== RCS file: /cvs/src/sys/kern/kern_task.c,v retrieving revision 1.19 diff -u -p -r1.19 kern_task.c --- kern/kern_task.c 14 Feb 2017 10:31:15 -0000 1.19 +++ kern/kern_task.c 12 Mar 2017 11:38:31 -0000 @@ -23,8 +23,6 @@ #include #include -#define TASK_ONQUEUE 1 - struct taskq { enum { TQ_S_CREATED, @@ -306,3 +304,11 @@ taskq_thread(void *xtq) kthread_exit(0); } + +static inline int +task_heap_cmp(const struct task *a, const struct task *b) +{ + return (a->t_deadline - b->t_deadline); +} + +HEAP_GENERATE(task_heap, task, _t_entry._t_heap, task_heap_cmp); Index: kern/subr_tree.c =================================================================== RCS file: /cvs/src/sys/kern/subr_tree.c,v retrieving revision 1.6 diff -u -p -r1.6 subr_tree.c --- kern/subr_tree.c 20 Sep 2016 01:11:27 -0000 1.6 +++ kern/subr_tree.c 12 Mar 2017 11:38:31 -0000 @@ -610,3 +610,181 @@ _rb_check(const struct rb_type *t, void (unsigned long)RBE_LEFT(rbe) == poison && (unsigned long)RBE_RIGHT(rbe) == poison); } + +static inline struct _heap_entry * +heap_n2e(const struct _heap_type *t, void *node) +{ + caddr_t addr = (caddr_t)node; + + return ((struct _heap_entry *)(addr + t->t_offset)); +} + +static inline void * +heap_e2n(const struct _heap_type *t, struct _heap_entry *he) +{ + caddr_t addr = (caddr_t)he; + + return ((void *)(addr - t->t_offset)); +} + +static struct _heap_entry * +_heap_merge(const struct _heap_type *t, + struct _heap_entry *he1, struct _heap_entry *he2) +{ + struct _heap_entry *hi, *lo; + struct _heap_entry *child; + + if (he1 == NULL) + return (he2); + if (he2 == NULL) + return (he1); + + if (t->t_compare(heap_e2n(t, he1), heap_e2n(t, he2)) >= 0) { + hi = he1; + lo = he2; + } else { + lo = he1; + hi = he2; + } + + child = lo->he_child; + + hi->he_left = lo; + hi->he_nextsibling = child; + if (child != NULL) + child->he_left = hi; + lo->he_child = hi; + lo->he_left = NULL; + lo->he_nextsibling = NULL; + + return (lo); +} + +static inline void +_heap_sibling_remove(struct _heap_entry *he) +{ + if (he->he_left == NULL) + return; + + if (he->he_left->he_child == he) { + if ((he->he_left->he_child = he->he_nextsibling) != NULL) + he->he_nextsibling->he_left = he->he_left; + } else { + if ((he->he_left->he_nextsibling = he->he_nextsibling) != NULL) + he->he_nextsibling->he_left = he->he_left; + } + + he->he_left = NULL; + he->he_nextsibling = NULL; +} + +static inline struct _heap_entry * +_heap_2pass_merge(const struct _heap_type *t, struct _heap_entry *root) +{ + struct _heap_entry *node, *next = NULL; + struct _heap_entry *tmp, *list = NULL; + + node = root->he_child; + if (node == NULL) + return (NULL); + + root->he_child = NULL; + + /* first pass */ + for (next = node->he_nextsibling; next != NULL; + next = (node != NULL ? node->he_nextsibling : NULL)) { + tmp = next->he_nextsibling; + node = _heap_merge(t, node, next); + + /* insert head */ + node->he_nextsibling = list; + list = node; + node = tmp; + } + + /* odd child case */ + if (node != NULL) { + node->he_nextsibling = list; + list = node; + } + + /* second pass */ + while (list->he_nextsibling != NULL) { + tmp = list->he_nextsibling->he_nextsibling; + list = _heap_merge(t, list, list->he_nextsibling); + list->he_nextsibling = tmp; + } + + list->he_left = NULL; + list->he_nextsibling = NULL; + + return (list); +} + +void +_heap_insert(const struct _heap_type *t, struct _heap *h, void *node) +{ + struct _heap_entry *he = heap_n2e(t, node); + + he->he_left = NULL; + he->he_child = NULL; + he->he_nextsibling = NULL; + + h->h_root = _heap_merge(t, h->h_root, he); +} + +void +_heap_remove(const struct _heap_type *t, struct _heap *h, void *node) +{ + struct _heap_entry *he = heap_n2e(t, node); + + if (he->he_left == NULL) { + _heap_extract(t, h); + return; + } + + _heap_sibling_remove(he); + h->h_root = _heap_merge(t, h->h_root, _heap_2pass_merge(t, he)); +} + +void * +_heap_first(const struct _heap_type *t, struct _heap *h) +{ + struct _heap_entry *first = h->h_root; + + if (first == NULL) + return (NULL); + + return (heap_e2n(t, first)); +} + +void * +_heap_extract(const struct _heap_type *t, struct _heap *h) +{ + struct _heap_entry *first = h->h_root; + + if (first == NULL) + return (NULL); + + h->h_root = _heap_2pass_merge(t, first); + + return (heap_e2n(t, first)); +} + +void * +_heap_cextract(const struct _heap_type *t, struct _heap *h, const void *key) +{ + struct _heap_entry *first = h->h_root; + void *node; + + if (first == NULL) + return (NULL); + + node = heap_e2n(t, first); + if (t->t_compare(node, key) > 0) + return (NULL); + + h->h_root = _heap_2pass_merge(t, first); + + return (node); +} Index: net/ifq.c =================================================================== RCS file: /cvs/src/sys/net/ifq.c,v retrieving revision 1.6 diff -u -p -r1.6 ifq.c --- net/ifq.c 24 Jan 2017 03:57:35 -0000 1.6 +++ net/ifq.c 12 Mar 2017 11:38:31 -0000 @@ -70,8 +70,6 @@ void ifq_start_task(void *); void ifq_restart_task(void *); void ifq_barrier_task(void *); -#define TASK_ONQUEUE 0x1 - void ifq_serialize(struct ifqueue *ifq, struct task *t) { Index: sys/proc.h =================================================================== RCS file: /cvs/src/sys/sys/proc.h,v retrieving revision 1.236 diff -u -p -r1.236 proc.h --- sys/proc.h 5 Mar 2017 06:40:18 -0000 1.236 +++ sys/proc.h 12 Mar 2017 11:38:31 -0000 @@ -45,6 +45,7 @@ #include /* For LOGIN_NAME_MAX */ #include #include /* For struct timeout */ +#include /* For struct task */ #include /* For struct klist */ #include /* For struct mutex */ #include /* For struct rusage */ @@ -305,6 +306,7 @@ struct proc { int p_cpticks; /* Ticks of cpu time. */ const volatile void *p_wchan;/* Sleep address. */ struct timeout p_sleep_to;/* timeout for tsleep() */ + struct task p_sleep_t;/* timeout for tsleep() */ const char *p_wmesg; /* Reason for sleep. */ fixpt_t p_pctcpu; /* %cpu for this thread */ u_int p_slptime; /* Time since last blocked. */ Index: sys/refcnt.h =================================================================== RCS file: /cvs/src/sys/sys/refcnt.h,v retrieving revision 1.4 diff -u -p -r1.4 refcnt.h --- sys/refcnt.h 7 Jun 2016 07:53:33 -0000 1.4 +++ sys/refcnt.h 12 Mar 2017 11:38:31 -0000 @@ -30,7 +30,7 @@ struct refcnt { void refcnt_init(struct refcnt *); void refcnt_take(struct refcnt *); int refcnt_rele(struct refcnt *); -void refcnt_rele_wake(struct refcnt *); +int refcnt_rele_wake(struct refcnt *); void refcnt_finalize(struct refcnt *, const char *); #endif /* _KERNEL */ Index: sys/systm.h =================================================================== RCS file: /cvs/src/sys/sys/systm.h,v retrieving revision 1.124 diff -u -p -r1.124 systm.h --- sys/systm.h 14 Feb 2017 09:46:21 -0000 1.124 +++ sys/systm.h 12 Mar 2017 11:38:31 -0000 @@ -252,6 +252,7 @@ void wakeup_n(const volatile void *, void wakeup(const volatile void *); #define wakeup_one(c) wakeup_n((c), 1) int tsleep(const volatile void *, int, const char *, int); +int utsleep(const volatile void *, int, const char *, int); int msleep(const volatile void *, struct mutex *, int, const char*, int); int rwsleep(const volatile void *, struct rwlock *, int, const char *, int); void yield(void); @@ -356,6 +357,10 @@ void user_config(void); #endif #if defined(MULTIPROCESSOR) +struct cpu_info; +struct task; +void cpu_xcall(struct cpu_info *, struct task *); + void _kernel_lock_init(void); void _kernel_lock(void); void _kernel_unlock(void); Index: sys/task.h =================================================================== RCS file: /cvs/src/sys/sys/task.h,v retrieving revision 1.11 diff -u -p -r1.11 task.h --- sys/task.h 7 Jun 2016 07:53:33 -0000 1.11 +++ sys/task.h 12 Mar 2017 11:38:31 -0000 @@ -20,26 +20,47 @@ #define _SYS_TASK_H_ #include +#include struct taskq; struct task { - TAILQ_ENTRY(task) t_entry; + union { + TAILQ_ENTRY(task) _t_list; + HEAP_ENTRY(task) _t_heap; + } _t_entry; +#define t_entry _t_entry._t_list + void (*t_func)(void *); void *t_arg; + unsigned int t_flags; + int t_deadline; }; TAILQ_HEAD(task_list, task); +HEAP_HEAD(task_heap); + +#define TASK_ONQUEUE 2 /* task is on the todo queue */ +#define TASK_INITIALIZED 4 /* task is initialized */ #define TASKQ_MPSAFE (1 << 0) #define TASKQ_CANTSLEEP (1 << 1) -#define TASK_INITIALIZER(_f, _a) {{ NULL, NULL }, (_f), (_a), 0 } +#define task_pending(_t) ((_t)->t_flags & TASK_ONQUEUE) +#define task_initialized(_t) ((_t)->t_flags & TASK_INITIALIZED) #ifdef _KERNEL +HEAP_PROTOTYPE(task_heap, task); + extern struct taskq *const systq; extern struct taskq *const systqmp; + +#define TASK_INITIALIZER(_f, _a) { \ + .t_func = (_f), \ + .t_arg = (_a), \ + .t_flags = TASK_INITIALIZED, \ +} struct taskq *taskq_create(const char *, unsigned int, int, unsigned int); void taskq_destroy(struct taskq *); Index: sys/tree.h =================================================================== RCS file: /cvs/src/sys/sys/tree.h,v retrieving revision 1.25 diff -u -p -r1.25 tree.h --- sys/tree.h 26 Sep 2016 08:08:51 -0000 1.25 +++ sys/tree.h 12 Mar 2017 11:38:31 -0000 @@ -984,4 +984,116 @@ RBT_GENERATE_INTERNAL(_name, _type, _fie #endif /* _KERNEL */ +struct _heap_type { + int (*t_compare)(const void *, const void *); + unsigned int t_offset; /* offset of heap_entry in type */ +}; + +struct _heap_entry { + struct _heap_entry *he_left; + struct _heap_entry *he_child; + struct _heap_entry *he_nextsibling; +}; +#define HEAP_ENTRY(_entry) struct _heap_entry + +struct _heap { + struct _heap_entry *h_root; +}; + +#define HEAP_HEAD(_name) \ +struct _name { \ + struct _heap heap; \ +} + +#ifdef _KERNEL + +static inline void +_heap_init(struct _heap *h) +{ + h->h_root = NULL; +} + +static inline int +_heap_empty(struct _heap *h) +{ + return (h->h_root == NULL); +} + +void _heap_insert(const struct _heap_type *, struct _heap *, void *); +void _heap_remove(const struct _heap_type *, struct _heap *, void *); +void *_heap_first(const struct _heap_type *, struct _heap *); +void *_heap_extract(const struct _heap_type *, struct _heap *); +void *_heap_cextract(const struct _heap_type *, struct _heap *, + const void *); + +#define HEAP_INITIALIZER(_head) { { NULL } } + +#define HEAP_PROTOTYPE(_name, _type) \ +extern const struct _heap_type *const _name##_HEAP_TYPE; \ + \ +static inline void \ +_name##_HEAP_INIT(struct _name *head) \ +{ \ + _heap_init(&head->heap); \ +} \ + \ +static inline void \ +_name##_HEAP_INSERT(struct _name *head, struct _type *elm) \ +{ \ + _heap_insert(_name##_HEAP_TYPE, &head->heap, elm); \ +} \ + \ +static inline void \ +_name##_HEAP_REMOVE(struct _name *head, struct _type *elm) \ +{ \ + _heap_remove(_name##_HEAP_TYPE, &head->heap, elm); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_FIRST(struct _name *head) \ +{ \ + return _heap_first(_name##_HEAP_TYPE, &head->heap); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_EXTRACT(struct _name *head) \ +{ \ + return _heap_extract(_name##_HEAP_TYPE, &head->heap); \ +} \ + \ +static inline struct _type * \ +_name##_HEAP_CEXTRACT(struct _name *head, const struct _type *key) \ +{ \ + return _heap_cextract(_name##_HEAP_TYPE, &head->heap, key); \ +} \ + \ +static inline int \ +_name##_HEAP_EMPTY(struct _name *head) \ +{ \ + return _heap_empty(&head->heap); \ +} + +#define HEAP_GENERATE(_name, _type, _field, _cmp) \ +static int \ +_name##_HEAP_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct _heap_type _name##_HEAP_INFO = { \ + _name##_HEAP_COMPARE, \ + offsetof(struct _type, _field), \ +}; \ +const struct _heap_type *const _name##_HEAP_TYPE = &_name##_HEAP_INFO + +#define HEAP_INIT(_name, _h) _name##_HEAP_INIT((_h)) +#define HEAP_INSERT(_name, _h, _e) _name##_HEAP_INSERT((_h), (_e)) +#define HEAP_REMOVE(_name, _h, _e) _name##_HEAP_REMOVE((_h), (_e)) +#define HEAP_FIRST(_name, _h) _name##_HEAP_FIRST((_h)) +#define HEAP_EXTRACT(_name, _h) _name##_HEAP_EXTRACT((_h)) +#define HEAP_CEXTRACT(_name, _h, _k) _name##_HEAP_CEXTRACT((_h), (_k)) +#define HEAP_EMPTY(_name, _h) _name##_HEAP_EMPTY((_h)) + +#endif /* _KERNEL */ + #endif /* _SYS_TREE_H_ */