/* $NetBSD: pthread_run.c,v 1.14 2003/12/07 20:29:07 christos Exp $ */ /*- * Copyright (c) 2001 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Nathan J. Williams. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the NetBSD * Foundation, Inc. and its contributors. * 4. Neither the name of The NetBSD Foundation nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include __RCSID("$NetBSD: pthread_run.c,v 1.14 2003/12/07 20:29:07 christos Exp $"); #include #include #include "pthread.h" #include "pthread_int.h" #ifdef PTHREAD_RUN_DEBUG #define SDPRINTF(x) DPRINTF(x) #else #define SDPRINTF(x) #endif extern pthread_spin_t pthread__runqueue_lock; extern struct pthread_queue_t pthread__runqueue; extern struct pthread_queue_t pthread__idlequeue; extern struct pthread_queue_t pthread__suspqueue; extern pthread_spin_t pthread__deadqueue_lock; extern struct pthread_queue_t pthread__reidlequeue; __strong_alias(__libc_thr_yield,sched_yield) int sched_yield(void) { pthread_t self, next; extern int pthread__started; if (pthread__started) { self = pthread__self(); SDPRINTF(("(sched_yield %p) yielding\n", self)); pthread_spinlock(self, &pthread__runqueue_lock); self->pt_state = PT_STATE_RUNNABLE; PTQ_INSERT_TAIL(&pthread__runqueue, self, pt_runq); /* * There will always be at least one thread on the runqueue, * because we just put ourselves there. */ next = PTQ_FIRST(&pthread__runqueue); PTQ_REMOVE(&pthread__runqueue, next, pt_runq); next->pt_state = PT_STATE_RUNNING; if (next != self) pthread__locked_switch(self, next, &pthread__runqueue_lock); else pthread_spinunlock(self, &pthread__runqueue_lock); } return 0; } /* Go do another thread, without putting us on the run queue. */ void pthread__block(pthread_t self, pthread_spin_t *queuelock) { pthread_t next; next = pthread__next(self); next->pt_state = PT_STATE_RUNNING; SDPRINTF(("(calling locked_switch %p, %p) spinlock %d, %d\n", self, next, self->pt_spinlocks, next->pt_spinlocks)); pthread__locked_switch(self, next, queuelock); SDPRINTF(("(back from locked_switch %p, %p) spinlock %d, %d\n", self, next, self->pt_spinlocks, next->pt_spinlocks)); } /* Get the next thread to switch to. Will never return NULL. */ pthread_t pthread__next(pthread_t self) { pthread_t next; pthread_spinlock(self, &pthread__runqueue_lock); next = PTQ_FIRST(&pthread__runqueue); if (next) { pthread__assert(next->pt_type == PT_THREAD_NORMAL); PTQ_REMOVE(&pthread__runqueue, next, pt_runq); } else { next = PTQ_FIRST(&pthread__idlequeue); pthread__assert(next != 0); PTQ_REMOVE(&pthread__idlequeue, next, pt_runq); pthread__assert(next->pt_type == PT_THREAD_IDLE); SDPRINTF(("(next %p) returning idle thread %p\n", self, next)); } pthread_spinunlock(self, &pthread__runqueue_lock); return next; } /* Put a thread on the suspended queue */ void pthread__suspend(pthread_t self, pthread_t thread) { SDPRINTF(("(sched %p) suspending %p\n", self, thread)); thread->pt_state = PT_STATE_SUSPENDED; pthread__assert(thread->pt_type == PT_THREAD_NORMAL); pthread__assert(thread->pt_spinlocks == 0); pthread_spinlock(self, &pthread__runqueue_lock); PTQ_INSERT_TAIL(&pthread__suspqueue, thread, pt_runq); pthread_spinunlock(self, &pthread__runqueue_lock); /* XXX flaglock? */ thread->pt_flags &= ~PT_FLAG_SUSPENDED; } /* Put a thread back on the run queue */ void pthread__sched(pthread_t self, pthread_t thread) { SDPRINTF(("(sched %p) scheduling %p\n", self, thread)); thread->pt_state = PT_STATE_RUNNABLE; pthread__assert(thread->pt_type == PT_THREAD_NORMAL); pthread__assert(thread->pt_spinlocks == 0); #ifdef PTHREAD__DEBUG thread->rescheds++; #endif pthread_spinlock(self, &pthread__runqueue_lock); PTQ_INSERT_TAIL(&pthread__runqueue, thread, pt_runq); pthread_spinunlock(self, &pthread__runqueue_lock); } /* Put a bunch of sleeping threads on the run queue */ void pthread__sched_sleepers(pthread_t self, struct pthread_queue_t *threadq) { pthread_t thread; pthread_spinlock(self, &pthread__runqueue_lock); PTQ_FOREACH(thread, threadq, pt_sleep) { SDPRINTF(("(sched_sleepers %p) scheduling %p\n", self, thread)); thread->pt_state = PT_STATE_RUNNABLE; pthread__assert(thread->pt_type == PT_THREAD_NORMAL); pthread__assert(thread->pt_spinlocks == 0); #ifdef PTHREAD__DEBUG thread->rescheds++; #endif PTQ_INSERT_TAIL(&pthread__runqueue, thread, pt_runq); } pthread_spinunlock(self, &pthread__runqueue_lock); } /* Make a thread a candidate idle thread. */ void pthread__sched_idle(pthread_t self, pthread_t thread) { SDPRINTF(("(sched_idle %p) idling %p\n", self, thread)); thread->pt_state = PT_STATE_RUNNABLE; thread->pt_flags &= ~PT_FLAG_IDLED; thread->pt_trapuc = NULL; _INITCONTEXT_U(thread->pt_uc); thread->pt_uc->uc_stack = thread->pt_stack; thread->pt_uc->uc_link = NULL; makecontext(thread->pt_uc, pthread__idle, 0); pthread_spinlock(self, &pthread__runqueue_lock); PTQ_INSERT_TAIL(&pthread__idlequeue, thread, pt_runq); pthread_spinunlock(self, &pthread__runqueue_lock); } void pthread__sched_idle2(pthread_t self) { pthread_t idlethread, qhead, next; /* XXXconcurrency: only reidle threads on same vp */ qhead = NULL; pthread_spinlock(self, &pthread__deadqueue_lock); idlethread = PTQ_FIRST(&pthread__reidlequeue); while (idlethread != NULL) { SDPRINTF(("(sched_idle2 %p) reidling %p\n", self, idlethread)); next = PTQ_NEXT(idlethread, pt_runq); if (idlethread->pt_next == NULL) { PTQ_REMOVE(&pthread__reidlequeue, idlethread, pt_runq); idlethread->pt_next = qhead; qhead = idlethread; } else { SDPRINTF(("(sched_idle2 %p) %p is in a preemption loop\n", self, idlethread)); } idlethread = next; } pthread_spinunlock(self, &pthread__deadqueue_lock); if (qhead) pthread__sched_bulk(self, qhead); } /* * Put a series of threads, linked by their pt_next fields, onto the * run queue. */ void pthread__sched_bulk(pthread_t self, pthread_t qhead) { pthread_t next; pthread_spinlock(self, &pthread__runqueue_lock); for ( ; qhead && (qhead != self) ; qhead = next) { next = qhead->pt_next; pthread__assert(qhead->pt_spinlocks == 0); pthread__assert(qhead->pt_type != PT_THREAD_UPCALL); if (qhead->pt_type == PT_THREAD_NORMAL) { qhead->pt_state = PT_STATE_RUNNABLE; qhead->pt_next = NULL; qhead->pt_parent = NULL; #ifdef PTHREAD__DEBUG qhead->rescheds++; #endif SDPRINTF(("(bulk %p) scheduling %p\n", self, qhead)); pthread__assert(PTQ_LAST(&pthread__runqueue, pthread_queue_t) != qhead); pthread__assert(PTQ_FIRST(&pthread__runqueue) != qhead); if (qhead->pt_flags & PT_FLAG_SUSPENDED) { qhead->pt_state = PT_STATE_SUSPENDED; PTQ_INSERT_TAIL(&pthread__suspqueue, qhead, pt_runq); } else PTQ_INSERT_TAIL(&pthread__runqueue, qhead, pt_runq); } else if (qhead->pt_type == PT_THREAD_IDLE) { qhead->pt_state = PT_STATE_RUNNABLE; qhead->pt_flags &= ~PT_FLAG_IDLED; qhead->pt_next = NULL; qhead->pt_parent = NULL; qhead->pt_trapuc = NULL; _INITCONTEXT_U(qhead->pt_uc); qhead->pt_uc->uc_stack = qhead->pt_stack; qhead->pt_uc->uc_link = NULL; makecontext(qhead->pt_uc, pthread__idle, 0); SDPRINTF(("(bulk %p) idling %p\n", self, qhead)); PTQ_INSERT_TAIL(&pthread__idlequeue, qhead, pt_runq); } } pthread_spinunlock(self, &pthread__runqueue_lock); } /*ARGSUSED*/ int pthread_getschedparam(pthread_t thread, int *policy, struct sched_param *param) { if (param == NULL || policy == NULL) return EINVAL; param->sched_priority = 0; *policy = SCHED_RR; return 0; } /*ARGSUSED*/ int pthread_setschedparam(pthread_t thread, int policy, const struct sched_param *param) { if (param == NULL || policy < SCHED_FIFO || policy > SCHED_RR) return EINVAL; if (param->sched_priority > 0 || policy != SCHED_RR) return ENOTSUP; return 0; } ome corner cases. Improve regression test and sprinkle some asserts. - npf_reassembly: clear nbuf on IPv6 reassembly failure path (partial fix). The problem was found and fix provided by Anthony Mallet. 2012-12-24- Rework NPF's nbuf interface: use advancing and ensuring as a main method.rmind Eliminate unnecessary copy and simplify. Adapt regression tests. - Simplify ICMP ALG a little. While here, handle ICMP ECHO for traceroute. - Minor fixes, misc cleanup. 2012-09-13Mark npf_session_worker as __dead.joerg 2012-08-12- Extend npftest: add ruleset inspection testing from the config generatedrmind by npfctl debug functionality. Auto-create npftest interfaces for this. - NPF sessions: combine protocol and interface into a separate substructure, share between the entries and thus fix the handling of them. Constify. - npftest: add regression tests for NAT policies. - npf_build_nat: simplify and fix bi-NAT regression. - Bump yacc stack size for npfctl. 2012-07-19teach npf ipv6-icmpspz reviewed by rmind@ 2012-07-15- Rework NPF tables and fix support for IPv6. Implement tree table typermind using radix / Patricia tree. Universal IPv4/IPv6 comparator for ptree(3) was contributed by Matt Thomas. - NPF tables: update regression tests, improve npfctl(8) error messages. - Fix few bugs when using kernel modules and handle module autounloader. - Few other fixes and misc cleanups. - Bump the version. 2012-07-01NPF improvements:rmind - Add NPF_OPCODE_PROTO to match the address and/or protocol only. - Update parser to support arbitrary "pass proto <name/number>". - Fix IPv6 address and protocol handling (add a regression test). - Fix few theorethical races in session handling module. - Misc fixes, simplifications and some clean up. 2012-06-22NPF:rmind - Rename some functions for consistency and de-inline them. - Fix few invalid asserts (add regressoin test). - Use pserialize(9) for ALG interface. - Minor fixes, sprinkle many comments. 2012-03-11- Save active config in proplib dictionary; add GETCONF ioctl to retrieve.rmind - Few fixes. Improve some comments. 2012-02-20- Add NPF_DECISION_BLOCK and NPF_DECISION_PASS. Be more defensive in thermind packet handler. Change the default policy to block when the config is loaded and set it to pass when flush operation is performed. - Use kmem_zalloc(9) instead of kmem_alloc(9) in few places. - npf_rproc_{create,release}: use kmem_intr_{alloc,free} as the destruction of rule procedure might happen in the interrupt handler (under a very rare condition, if config reload races with the handler). - npf_session_establish: check whether layer 3 and 4 are cached. - npfctl_build_group: do not make groups as passing rules. - Remove some unecessary header inclusion. 2011-11-29- Rework and improve TCP state tracking.rmind - Fix regressions after IPv6 patch merge. Note: npfctl(8) rework will come soon. 2011-11-04Add IPv6 support for NPF.zoltan 2011-02-02NPF checkpoint:rmind - Add libnpf(3) - a library to control NPF (configuration, ruleset, etc). - Add NPF support for ftp-proxy(8). - Add rc.d script for NPF. - Convert npfctl(8) to use libnpf(3) and thus make it less depressive. Note: next clean-up step should be a parser, once dholland@ will finish it. - Add more documentation. - Various fixes. 2011-01-18NPF checkpoint:rmind - Add the concept of rule procedure: separate normalization, logging and potentially other functions from the rule structure. Rule procedure can be shared amongst the rules. Separation is both at kernel level (npf_rproc_t) and configuration ("procedure" + "apply"). - Fix portmap sharing for NAT policy. - Update TCP state tracking logic. Use TCP FSM definitions. - Add if_byindex(), OK by matt@. Use in logging for the lookup. - Fix traceroute ALG and many other bugs; misc clean-up. 2010-12-18NPF checkpoint:rmind - Add support for session saving/restoring. - Add packet logging support (can tcpdump a pseudo-interface). - Support reload without flushing of sessions; rework some locking. - Revisit session mangement, replace linking with npf_sentry_t entries. - Add some counters for statistics, using percpu(9). - Add IP_DF flag cleansing. - Fix various bugs; misc clean-up. 2010-11-11NPF checkpoint:rmind - Add proper TCP state tracking as described in Guido van Rooij paper, plus handle TCP Window Scaling option. - Completely rework npf_cache_t, reduce granularity, simplify code. - Add npf_addr_t as an abstraction, amend session handling code, as well as NAT code et al, to use it. Now design is prepared for IPv6 support. - Handle IPv4 fragments i.e. perform packet reassembly. - Add support for IPv4 ID randomization and minimum TTL enforcement. - Add support for TCP MSS "clamping". - Random bits for IPv6. Various fixes and clean-up. 2010-10-03- npf_session_gc: fix for previous RB-tree conversion.rmind - npf_session_free: rename (to singular). 2010-09-24Fixes/improvements to RB-tree implementation:rmind 1. Fix inverted node order, so that negative value from comparison operator would represent lower (left) node, and positive - higher (right) node. 2. Add an argument (i.e. "context"), passed to comparison operators. 3. Change rb_tree_insert_node() to return a node - either inserted one or already existing one. 4. Amend the interface to manipulate the actual object, instead of the rb_node (in a similar way as Patricia-tree interface does). 5. Update all RB-tree users accordingly. XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up.. 1-3 address the PR/43488 by Jeremy Huddleston. Passes RB-tree regression tests. Reviewed by: matt@, christos@ 2010-09-16NPF checkpoint:rmind - Add support for bi-directional NAT and redirection / port forwarding. - Finish filtering on ICMP type/code and add filtering on TCP flags. - Add support for TCP reset (RST) or ICMP destination unreachable on block. - Fix a bunch of bugs; misc cleanup. 2010-08-22Import NPF - a packet filter. Some features:rmind - Designed to be fully MP-safe and highly efficient. - Tables/IP sets (hash or red-black tree) for high performance lookups. - Stateful filtering and Network Address Port Translation (NAPT). Framework for application level gateways (ALGs). - Packet inspection engine called n-code processor - inspired by BPF - supporting generic RISC-like and specific CISC-like instructions for common patterns (e.g. IPv4 address matching). See npf_ncode(9) manual. - Convenient userland utility npfctl(8) with npf.conf(8). NOTE: This is not yet a fully capable alternative to PF or IPFilter. Further work (support for binat/rdr, return-rst/return-icmp, common ALGs, state saving/restoring, logging, etc) is in progress. Thanks a lot to Matt Thomas for various useful comments and code review. Aye by: board@