From owner-svn-src-all@FreeBSD.ORG Tue Apr 13 19:37:18 2010 Return-Path: Delivered-To: svn-src-all@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 7F9EC106566C; Tue, 13 Apr 2010 19:37:18 +0000 (UTC) (envelope-from rdivacky@vlk.vlakno.cz) Received: from vlakno.cz (lev.vlakno.cz [77.93.215.190]) by mx1.freebsd.org (Postfix) with ESMTP id 880758FC1A; Tue, 13 Apr 2010 19:37:16 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by vlakno.cz (Postfix) with ESMTP id 67F479CB0E4; Tue, 13 Apr 2010 21:35:03 +0200 (CEST) X-Virus-Scanned: amavisd-new at vlakno.cz Received: from vlakno.cz ([127.0.0.1]) by localhost (lev.vlakno.cz [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id x5lKU-zrBDGu; Tue, 13 Apr 2010 21:35:00 +0200 (CEST) Received: from vlk.vlakno.cz (localhost [127.0.0.1]) by vlakno.cz (Postfix) with ESMTP id 4CFEC9CB25F; Tue, 13 Apr 2010 21:35:00 +0200 (CEST) Received: (from rdivacky@localhost) by vlk.vlakno.cz (8.14.3/8.14.3/Submit) id o3DJZ0Vg046947; Tue, 13 Apr 2010 21:35:00 +0200 (CEST) (envelope-from rdivacky) Date: Tue, 13 Apr 2010 21:35:00 +0200 From: Roman Divacky To: Luigi Rizzo Message-ID: <20100413193500.GA46839@freebsd.org> References: <201004121637.o3CGbjSK080066@svn.freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <201004121637.o3CGbjSK080066@svn.freebsd.org> User-Agent: Mutt/1.4.2.3i Cc: svn-src-head@FreeBSD.org, svn-src-all@FreeBSD.org, src-committers@FreeBSD.org Subject: Re: svn commit: r206497 - in head: sbin/geom/class sbin/geom/class/sched sys/geom/sched sys/modules/geom sys/modules/geom/geom_sched sys/modules/geom/geom_sched/gs_sched sys/modules/geom/geom_sched/gsc... X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Apr 2010 19:37:18 -0000 you dont seem to have commited the anticipatory scheduler gsched_as. why? On Mon, Apr 12, 2010 at 04:37:45PM +0000, Luigi Rizzo wrote: > Author: luigi > Date: Mon Apr 12 16:37:45 2010 > New Revision: 206497 > URL: http://svn.freebsd.org/changeset/base/206497 > > Log: > Bring in geom_sched, support for scheduling disk I/O requests > in a device independent manner. Also include an example anticipatory > scheduler, gsched_rr, which gives very nice performance improvements > in presence of competing random access patterns. > > This is joint work with Fabio Checconi, developed last year > and presented at BSDCan 2009. You can find details in the > README file or at > > http://info.iet.unipi.it/~luigi/geom_sched/ > > Added: > head/sbin/geom/class/sched/ > head/sbin/geom/class/sched/Makefile (contents, props changed) > head/sbin/geom/class/sched/geom_sched.c (contents, props changed) > head/sbin/geom/class/sched/gsched.8 (contents, props changed) > head/sys/geom/sched/ > head/sys/geom/sched/README (contents, props changed) > head/sys/geom/sched/g_sched.c (contents, props changed) > head/sys/geom/sched/g_sched.h (contents, props changed) > head/sys/geom/sched/gs_rr.c (contents, props changed) > head/sys/geom/sched/gs_scheduler.h (contents, props changed) > head/sys/geom/sched/subr_disk.c (contents, props changed) > head/sys/modules/geom/geom_sched/ > head/sys/modules/geom/geom_sched/Makefile (contents, props changed) > head/sys/modules/geom/geom_sched/Makefile.inc (contents, props changed) > head/sys/modules/geom/geom_sched/gs_sched/ > head/sys/modules/geom/geom_sched/gs_sched/Makefile (contents, props changed) > head/sys/modules/geom/geom_sched/gsched_rr/ > head/sys/modules/geom/geom_sched/gsched_rr/Makefile (contents, props changed) > Modified: > head/sbin/geom/class/Makefile > head/sys/modules/geom/Makefile > > Modified: head/sbin/geom/class/Makefile > ============================================================================== > --- head/sbin/geom/class/Makefile Mon Apr 12 13:46:20 2010 (r206496) > +++ head/sbin/geom/class/Makefile Mon Apr 12 16:37:45 2010 (r206497) > @@ -15,6 +15,7 @@ SUBDIR+=multipath > SUBDIR+=nop > SUBDIR+=part > SUBDIR+=raid3 > +SUBDIR+=sched > SUBDIR+=shsec > SUBDIR+=stripe > SUBDIR+=virstor > > Added: head/sbin/geom/class/sched/Makefile > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sbin/geom/class/sched/Makefile Mon Apr 12 16:37:45 2010 (r206497) > @@ -0,0 +1,19 @@ > +# GEOM_LIBRARY_PATH > +# $FreeBSD$ > + > +.PATH: /usr/src/sbin/geom/misc > + > +CFLAGS += -I/usr/src/sbin/geom > + > +CLASS=sched > + > +WARNS?= 6 > +CLASS_DIR?=/lib/geom > + > +SHLIBDIR?=${CLASS_DIR} > +SHLIB_NAME?=geom_${CLASS}.so > +LINKS= ${BINDIR}/geom ${BINDIR}/g${CLASS} > +MAN= g${CLASS}.8 > +SRCS+= geom_${CLASS}.c subr.c > + > +.include > > Added: head/sbin/geom/class/sched/geom_sched.c > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sbin/geom/class/sched/geom_sched.c Mon Apr 12 16:37:45 2010 (r206497) > @@ -0,0 +1,123 @@ > +/*- > + * Copyright (c) 2009 Fabio Checconi, Luigi Rizzo > + * All rights reserved. > + * > + * 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. > + * > + * THIS SOFTWARE IS PROVIDED BY THE AUTHORS 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 AUTHORS 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. > + */ > + > +/* > + * $Id$ > + * $FreeBSD$ > + * > + * This file implements the userspace library used by the 'geom' > + * command to load and manipulate disk schedulers. > + */ > + > +#include > +#include > +#include > +#include > + > +#include > +#include > +#include > + > +#include "core/geom.h" > +#include "misc/subr.h" > + > +#define G_SCHED_VERSION 0 > + > +uint32_t lib_version = G_LIB_VERSION; > +uint32_t version = G_SCHED_VERSION; > + > +/* > + * storage for parameters used by this geom class. > + * Right now only the scheduler name is used. > + */ > +static char algo[] = "rr"; /* default scheduler */ > + > +/* > + * Adapt to differences in geom library. > + * in V1 struct g_command misses gc_argname, eld, and G_BOOL is undefined > + */ > +#if G_LIB_VERSION == 1 > +#define G_ARGNAME > +#define G_TYPE_BOOL G_TYPE_NUMBER > +#else > +#define G_ARGNAME NULL, > +#endif > + > +static void > +gcmd_createinsert(struct gctl_req *req, unsigned flags __unused) > +{ > + const char *reqalgo; > + char name[64]; > + > + if (gctl_has_param(req, "algo")) > + reqalgo = gctl_get_ascii(req, "algo"); > + else > + reqalgo = algo; > + > + snprintf(name, sizeof(name), "gsched_%s", reqalgo); > + /* > + * Do not complain about errors here, gctl_issue() > + * will fail anyway. > + */ > + if (modfind(name) < 0) > + kldload(name); > + gctl_issue(req); > +} > + > +struct g_command class_commands[] = { > + { "create", G_FLAG_VERBOSE | G_FLAG_LOADKLD, gcmd_createinsert, > + { > + { 'a', "algo", algo, G_TYPE_STRING }, > + G_OPT_SENTINEL > + }, > + G_ARGNAME "[-v] [-a algorithm_name] dev ..." > + }, > + { "insert", G_FLAG_VERBOSE | G_FLAG_LOADKLD, gcmd_createinsert, > + { > + { 'a', "algo", algo, G_TYPE_STRING }, > + G_OPT_SENTINEL > + }, > + G_ARGNAME "[-v] [-a algorithm_name] dev ..." > + }, > + { "configure", G_FLAG_VERBOSE, NULL, > + { > + { 'a', "algo", algo, G_TYPE_STRING }, > + G_OPT_SENTINEL > + }, > + G_ARGNAME "[-v] [-a algorithm_name] prov ..." > + }, > + { "destroy", G_FLAG_VERBOSE, NULL, > + { > + { 'f', "force", NULL, G_TYPE_BOOL }, > + G_OPT_SENTINEL > + }, > + G_ARGNAME "[-fv] prov ..." > + }, > + { "reset", G_FLAG_VERBOSE, NULL, G_NULL_OPTS, > + G_ARGNAME "[-v] prov ..." > + }, > + G_CMD_SENTINEL > +}; > > Added: head/sbin/geom/class/sched/gsched.8 > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sbin/geom/class/sched/gsched.8 Mon Apr 12 16:37:45 2010 (r206497) > @@ -0,0 +1,161 @@ > +.\" Copyright (c) 2009-2010 Fabio Checconi, Luigi Rizzo > +.\" All rights reserved. > +.\" $FreeBSD$ > +.\" > +.\" 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. > +.\" > +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHORS 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 AUTHORS 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. > +.\" > +.Dd April 12, 2010 > +.Dt GSCHED 8 > +.Os > +.Sh NAME > +.Nm gsched > +.Nd "control utility for disk scheduler GEOM class" > +.Sh SYNOPSIS > +.Nm > +.Cm create > +.Op Fl v > +.Op Fl a Ar algorithm > +.Ar provider ... > +.Nm > +.Cm insert > +.Op Fl v > +.Op Fl a Ar algorithm > +.Ar provider ... > +.Nm > +.Cm configure > +.Op Fl v > +.Op Fl a Ar algorithm > +.Ar node ... > +.Nm > +.Cm destroy > +.Op Fl fv > +.Ar node ... > +.Nm > +.Cm reset > +.Op Fl v > +.Ar node ... > +.Nm > +.Cm { list | status | load | unload } > +.Sh DESCRIPTION > +The > +.Nm > +utility (also callable as > +.Nm geom sched ... ) > +changes the scheduling policy of the requests going to a provider. > +.Pp > +The first argument to > +.Nm > +indicates an action to be performed: > +.Bl -tag -width ".Cm configure" > +.It Cm create > +Create a new provider and geom node using the specified scheduling algorithm. > +.Ar algorithm > +is the name of the scheduling algorithm used for the provider. > +Available algorithms include: > +.Ar rr , > +which implements anticipatory scheduling with round robin service > +among clients; > +.Ar as , > +which implements a simple form of anticipatory scheduling with > +no per-client queue. > +.Pp > +If the operation succeeds, the new provider should appear with name > +.Pa /dev/ Ns Ao Ar dev Ac Ns Pa .sched. . > +The kernel module > +.Pa geom_sched.ko > +will be loaded if it is not loaded already. > +.It Cm insert > +Operates as "create", but the insertion is "transparent", > +i.e. the existing provider is rerouted to the newly created geom, > +which in turn forwards requests to the existing geom. > +This operation allows one to start/stop a scheduling service > +on an already existing provider. > +.Pp > +A subsequent 'destroy' will remove the newly created geom and > +hook the provider back to the original geom. > +.Ar algorithm > +.It Cm configure > +Configure existing scheduling provider. It supports the same options > +as the > +.Nm create > +command. > +.It Cm destroy > +Destroy the geom specified in the parameter. > +.It Cm reset > +Do nothing. > +.It Cm list | status | load | unload > +See > +.Xr geom 8 . > +.El > +.Pp > +Additional options: > +.Bl -tag -width ".Fl f" > +.It Fl f > +Force the removal of the specified provider. > +.It Fl v > +Be more verbose. > +.El > +.Sh SYSCTL VARIABLES > +The following > +.Xr sysctl 8 > +variables can be used to control the behavior of the > +.Nm SCHED > +GEOM class. > +The default value is shown next to each variable. > +.Bl -tag -width indent > +.It Va kern.geom.sched.debug : No 0 > +Debug level of the > +.Nm SCHED > +GEOM class. > +This can be set to a number between 0 and 2 inclusive. > +If set to 0 minimal debug information is printed, and if set to 2 the > +maximum amount of debug information is printed. > +.El > +.Sh EXIT STATUS > +Exit status is 0 on success, and 1 if the command fails. > +.Sh EXAMPLES > +The following example shows how to create a scheduling provider for disk > +.Pa /dev/da0 > +, and how to destroy it. > +.Bd -literal -offset indent > +# Load the geom_sched module: > +kldload geom_sched > +# Load some scheduler classes used by geom_sched: > +kldload gsched_rr gsched_as > +# Configure device ad0 to use scheduler 'rr': > +geom sched insert -s rr ad0 > +# Now provider ad0 uses the 'rr' algorithm; > +# the new geom is ad0.sched. > +# Remove the scheduler on the device: > +geom sched destroy -v ad0.sched. > +.Ed > +.Pp > +.Sh SEE ALSO > +.Xr geom 4 , > +.Xr geom 8 > +.Sh HISTORY > +The > +.Nm > +utility appeared in April 2010. > +.Sh AUTHORS > +.An Fabio Checconi Aq fabio@FreeBSD.org > +.An Luigi Rizzo Aq luigi@FreeBSD.org > > Added: head/sys/geom/sched/README > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sys/geom/sched/README Mon Apr 12 16:37:45 2010 (r206497) > @@ -0,0 +1,162 @@ > + > + --- GEOM BASED DISK SCHEDULERS FOR FREEBSD --- > + > +This code contains a framework for GEOM-based disk schedulers and a > +couple of sample scheduling algorithms that use the framework and > +implement two forms of "anticipatory scheduling" (see below for more > +details). > + > +As a quick example of what this code can give you, try to run "dd", > +"tar", or some other program with highly SEQUENTIAL access patterns, > +together with "cvs", "cvsup", "svn" or other highly RANDOM access patterns > +(this is not a made-up example: it is pretty common for developers > +to have one or more apps doing random accesses, and others that do > +sequential accesses e.g., loading large binaries from disk, checking > +the integrity of tarballs, watching media streams and so on). > + > +These are the results we get on a local machine (AMD BE2400 dual > +core CPU, SATA 250GB disk): > + > + /mnt is a partition mounted on /dev/ad0s1f > + > + cvs: cvs -d /mnt/home/ncvs-local update -Pd /mnt/ports > + dd-read: dd bs=128k of=/dev/null if=/dev/ad0 (or ad0-sched-) > + dd-writew dd bs=128k if=/dev/zero of=/mnt/largefile > + > + NO SCHEDULER RR SCHEDULER > + dd cvs dd cvs > + > + dd-read only 72 MB/s ---- 72 MB/s --- > + dd-write only 55 MB/s --- 55 MB/s --- > + dd-read+cvs 6 MB/s ok 30 MB/s ok > + dd-write+cvs 55 MB/s slooow 14 MB/s ok > + > +As you can see, when a cvs is running concurrently with dd, the > +performance drops dramatically, and depending on read or write mode, > +one of the two is severely penalized. The use of the RR scheduler > +in this example makes the dd-reader go much faster when competing > +with cvs, and lets cvs progress when competing with a writer. > + > +To try it out: > + > +1. USERS OF FREEBSD 7, PLEASE READ CAREFULLY THE FOLLOWING: > + > + On loading, this module patches one kernel function (g_io_request()) > + so that I/O requests ("bio's") carry a classification tag, useful > + for scheduling purposes. > + > + ON FREEBSD 7, the tag is stored in an existing (though rarely used) > + field of the "struct bio", a solution which makes this module > + incompatible with other modules using it, such as ZFS and gjournal. > + Additionally, g_io_request() is patched in-memory to add a call > + to the function that initializes this field (i386/amd64 only; > + for other architectures you need to manually patch sys/geom/geom_io.c). > + See details in the file g_sched.c. > + > + On FreeBSD 8.0 and above, the above trick is not necessary, > + as the struct bio contains dedicated fields for the classifier, > + and hooks for request classifiers. > + > + If you don't like the above, don't run this code. > + > +2. PLEASE MAKE SURE THAT THE DISK THAT YOU WILL BE USING FOR TESTS > + DOES NOT CONTAIN PRECIOUS DATA. > + This is experimental code, so we make no guarantees, though > + I am routinely using it on my desktop and laptop. > + > +3. EXTRACT AND BUILD THE PROGRAMS > + A 'make install' in the directory should work (with root privs), > + or you can even try the binary modules. > + If you want to build the modules yourself, look at the Makefile. > + > +4. LOAD THE MODULE, CREATE A GEOM NODE, RUN TESTS > + > + The scheduler's module must be loaded first: > + > + # kldload gsched_rr > + > + substitute with gsched_as to test AS. Then, supposing that you are > + using /dev/ad0 for testing, a scheduler can be attached to it with: > + > + # geom sched insert ad0 > + > + The scheduler is inserted transparently in the geom chain, so > + mounted partitions and filesystems will keep working, but > + now requests will go through the scheduler. > + > + To change scheduler on-the-fly, you can reconfigure the geom: > + > + # geom sched configure -a as ad0.sched. > + > + assuming that gsched_as was loaded previously. > + > +5. SCHEDULER REMOVAL > + > + In principle it is possible to remove the scheduler module > + even on an active chain by doing > + > + # geom sched destroy ad0.sched. > + > + However, there is some race in the geom subsystem which makes > + the removal unsafe if there are active requests on a chain. > + So, in order to reduce the risk of data losses, make sure > + you don't remove a scheduler from a chain with ongoing transactions. > + > +--- NOTES ON THE SCHEDULERS --- > + > +The important contribution of this code is the framework to experiment > +with different scheduling algorithms. 'Anticipatory scheduling' > +is a very powerful technique based on the following reasoning: > + > + The disk throughput is much better if it serves sequential requests. > + If we have a mix of sequential and random requests, and we see a > + non-sequential request, do not serve it immediately but instead wait > + a little bit (2..5ms) to see if there is another one coming that > + the disk can serve more efficiently. > + > +There are many details that should be added to make sure that the > +mechanism is effective with different workloads and systems, to > +gain a few extra percent in performance, to improve fairness, > +insulation among processes etc. A discussion of the vast literature > +on the subject is beyond the purpose of this short note. > + > +-------------------------------------------------------------------------- > + > +TRANSPARENT INSERT/DELETE > + > +geom_sched is an ordinary geom module, however it is convenient > +to plug it transparently into the geom graph, so that one can > +enable or disable scheduling on a mounted filesystem, and the > +names in /etc/fstab do not depend on the presence of the scheduler. > + > +To understand how this works in practice, remember that in GEOM > +we have "providers" and "geom" objects. > +Say that we want to hook a scheduler on provider "ad0", > +accessible through pointer 'pp'. Originally, pp is attached to > +geom "ad0" (same name, different object) accessible through pointer old_gp > + > + BEFORE ---> [ pp --> old_gp ...] > + > +A normal "geom sched create ad0" call would create a new geom node > +on top of provider ad0/pp, and export a newly created provider > +("ad0.sched." accessible through pointer newpp). > + > + AFTER create ---> [ newpp --> gp --> cp ] ---> [ pp --> old_gp ... ] > + > +On top of newpp, a whole tree will be created automatically, and we > +can e.g. mount partitions on /dev/ad0.sched.s1d, and those requests > +will go through the scheduler, whereas any partition mounted on > +the pre-existing device entries will not go through the scheduler. > + > +With the transparent insert mechanism, the original provider "ad0"/pp > +is hooked to the newly created geom, as follows: > + > + AFTER insert ---> [ pp --> gp --> cp ] ---> [ newpp --> old_gp ... ] > + > +so anything that was previously using provider pp will now have > +the requests routed through the scheduler node. > + > +A removal ("geom sched destroy ad0.sched.") will restore the original > +configuration. > + > +# $FreeBSD$ > > Added: head/sys/geom/sched/g_sched.c > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sys/geom/sched/g_sched.c Mon Apr 12 16:37:45 2010 (r206497) > @@ -0,0 +1,1901 @@ > +/*- > + * Copyright (c) 2009-2010 Fabio Checconi, Luigi Rizzo > + * All rights reserved. > + * > + * 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. > + * > + * THIS SOFTWARE IS PROVIDED BY THE AUTHORS 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 AUTHORS 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. > + */ > + > +/* > + * $Id$ > + * $FreeBSD$ > + * > + * Main control module for geom-based disk schedulers ('sched'). > + * > + * USER VIEW > + * A 'sched' node is typically inserted transparently between > + * an existing provider pp and its original geom gp > + * > + * [pp --> gp ..] > + * > + * using the command "geom sched insert " and > + * resulting in the following topology > + * > + * [pp --> sched_gp --> cp] [new_pp --> gp ... ] > + * > + * Deletion "geom sched destroy .sched." restores the > + * original chain. The normal "geom sched create " > + * is also supported. > + * > + * INTERNALS > + * Internally, the 'sched' uses the following data structures > + * > + * geom{} g_sched_softc{} g_gsched{} > + * +----------+ +---------------+ +-------------+ > + * | softc *-|--->| sc_gsched *-|-->| gs_init | > + * | ... | | | | gs_fini | > + * | | | [ hash table] | | gs_start | > + * +----------+ | | | ... | > + * | | +-------------+ > + * | | > + * | | g_*_softc{} > + * | | +-------------+ > + * | sc_data *-|-->| | > + * +---------------+ | algorithm- | > + * | specific | > + * +-------------+ > + * > + * A g_sched_softc{} is created with a "geom sched insert" call. > + * In turn this instantiates a specific scheduling algorithm, > + * which sets sc_gsched to point to the algorithm callbacks, > + * and calls gs_init() to create the g_*_softc{} . > + * The other callbacks (gs_start, gs_next, ...) are invoked > + * as needed > + * > + * g_sched_softc{} is defined in g_sched.h and mostly used here; > + * g_gsched{}, and the gs_callbacks, are documented in gs_scheduler.h; > + * g_*_softc{} is defined/implemented by each algorithm (gs_*.c) > + * > + * DATA MOVING > + * When a bio is received on the provider, it goes to the > + * g_sched_start() which calls gs_start() to initially queue it; > + * then we call g_sched_dispatch() that loops around gs_next() > + * to select zero or more bio's to be sent downstream. > + * > + * g_sched_dispatch() can also be called as a result of a timeout, > + * e.g. when doing anticipation or pacing requests. > + * > + * When a bio comes back, it goes to g_sched_done() which in turn > + * calls gs_done(). The latter does any necessary housekeeping in > + * the scheduling algorithm, and may decide to call g_sched_dispatch() > + * to send more bio's downstream. > + * > + * If an algorithm needs per-flow queues, these are created > + * calling gs_init_class() and destroyed with gs_fini_class(), > + * and they are also inserted in the hash table implemented in > + * the g_sched_softc{} > + * > + * If an algorithm is replaced, or a transparently-inserted node is > + * removed with "geom sched destroy", we need to remove all references > + * to the g_*_softc{} and g_sched_softc from the bio's still in > + * the scheduler. g_sched_forced_dispatch() helps doing this. > + * XXX need to explain better. > + */ > + > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include > +#include /* we access curthread */ > +#include > +#include "gs_scheduler.h" > +#include "g_sched.h" /* geom hooks */ > + > +/* > + * Size of the per-geom hash table storing traffic classes. > + * We may decide to change it at a later time, it has no ABI > + * implications as it is only used for run-time allocations. > + */ > +#define G_SCHED_HASH_SIZE 32 > + > +static int g_sched_destroy(struct g_geom *gp, boolean_t force); > +static int g_sched_destroy_geom(struct gctl_req *req, > + struct g_class *mp, struct g_geom *gp); > +static void g_sched_config(struct gctl_req *req, struct g_class *mp, > + const char *verb); > +static struct g_geom *g_sched_taste(struct g_class *mp, > + struct g_provider *pp, int flags __unused); > +static void g_sched_dumpconf(struct sbuf *sb, const char *indent, > + struct g_geom *gp, struct g_consumer *cp, struct g_provider *pp); > +static void g_sched_init(struct g_class *mp); > +static void g_sched_fini(struct g_class *mp); > + > +struct g_class g_sched_class = { > + .name = G_SCHED_CLASS_NAME, > + .version = G_VERSION, > + .ctlreq = g_sched_config, > + .taste = g_sched_taste, > + .destroy_geom = g_sched_destroy_geom, > + .init = g_sched_init, > + .fini = g_sched_fini > +}; > + > +MALLOC_DEFINE(M_GEOM_SCHED, "GEOM_SCHED", "Geom schedulers data structures"); > + > +/* > + * Global variables describing the state of the geom_sched module. > + * There is only one static instance of this structure. > + */ > +LIST_HEAD(gs_list, g_gsched); /* type, link field */ > +struct geom_sched_vars { > + struct mtx gs_mtx; > + struct gs_list gs_scheds; /* list of algorithms */ > + u_int gs_debug; > + u_int gs_sched_count; /* how many algorithms ? */ > + u_int gs_patched; /* g_io_request was patched */ > + > + u_int gs_initialized; > + u_int gs_expire_secs; /* expiration of hash entries */ > + > + struct bio_queue_head gs_pending; > + u_int gs_npending; > + > + /* The following are for stats, usually protected by gs_mtx. */ > + u_long gs_requests; /* total requests */ > + u_long gs_done; /* total done */ > + u_int gs_in_flight; /* requests in flight */ > + u_int gs_writes_in_flight; > + u_int gs_bytes_in_flight; > + u_int gs_write_bytes_in_flight; > + > + char gs_names[256]; /* names of schedulers */ > +}; > + > +static struct geom_sched_vars me = { > + .gs_expire_secs = 10, > +}; > + > +SYSCTL_DECL(_kern_geom); > +SYSCTL_NODE(_kern_geom, OID_AUTO, sched, CTLFLAG_RW, 0, > + "GEOM_SCHED stuff"); > + > +SYSCTL_INT(_kern_geom_sched, OID_AUTO, in_flight_wb, CTLFLAG_RD, > + &me.gs_write_bytes_in_flight, 0, "Write bytes in flight"); > + > +SYSCTL_INT(_kern_geom_sched, OID_AUTO, in_flight_b, CTLFLAG_RD, > + &me.gs_bytes_in_flight, 0, "Bytes in flight"); > + > +SYSCTL_UINT(_kern_geom_sched, OID_AUTO, in_flight_w, CTLFLAG_RD, > + &me.gs_writes_in_flight, 0, "Write Requests in flight"); > + > +SYSCTL_UINT(_kern_geom_sched, OID_AUTO, in_flight, CTLFLAG_RD, > + &me.gs_in_flight, 0, "Requests in flight"); > + > +SYSCTL_ULONG(_kern_geom_sched, OID_AUTO, done, CTLFLAG_RD, > + &me.gs_done, 0, "Total done"); > + > +SYSCTL_ULONG(_kern_geom_sched, OID_AUTO, requests, CTLFLAG_RD, > + &me.gs_requests, 0, "Total requests"); > + > +SYSCTL_STRING(_kern_geom_sched, OID_AUTO, algorithms, CTLFLAG_RD, > + &me.gs_names, 0, "Algorithm names"); > + > +SYSCTL_UINT(_kern_geom_sched, OID_AUTO, alg_count, CTLFLAG_RD, > + &me.gs_sched_count, 0, "Number of algorithms"); > + > +SYSCTL_UINT(_kern_geom_sched, OID_AUTO, debug, CTLFLAG_RW, > + &me.gs_debug, 0, "Debug level"); > + > +SYSCTL_UINT(_kern_geom_sched, OID_AUTO, expire_secs, CTLFLAG_RW, > + &me.gs_expire_secs, 0, "Expire time in seconds"); > + > +/* > + * g_sched calls the scheduler algorithms with this lock held. > + * The locking functions are exposed so the scheduler algorithms can also > + * protect themselves e.g. when running a callout handler. > + */ > +void > +g_sched_lock(struct g_geom *gp) > +{ > + struct g_sched_softc *sc = gp->softc; > + > + mtx_lock(&sc->sc_mtx); > +} > + > +void > +g_sched_unlock(struct g_geom *gp) > +{ > + struct g_sched_softc *sc = gp->softc; > + > + mtx_unlock(&sc->sc_mtx); > +} > + > +/* > + * Support functions to handle references to the module, > + * which are coming from devices using this scheduler. > + */ > +static inline void > +g_gsched_ref(struct g_gsched *gsp) > +{ > + > + atomic_add_int(&gsp->gs_refs, 1); > +} > + > +static inline void > +g_gsched_unref(struct g_gsched *gsp) > +{ > + > + atomic_add_int(&gsp->gs_refs, -1); > +} > + > +/* > + * Update the stats when this request is done. > + */ > +static void > +g_sched_update_stats(struct bio *bio) > +{ > + > + me.gs_done++; > + me.gs_in_flight--; > + me.gs_bytes_in_flight -= bio->bio_length; > + if (bio->bio_cmd & BIO_WRITE) { > + me.gs_writes_in_flight--; > + me.gs_write_bytes_in_flight -= bio->bio_length; > + } > +} > + > +/* > + * Dispatch any pending request. > + */ > +static void > +g_sched_forced_dispatch(struct g_geom *gp) > +{ > + struct g_sched_softc *sc = gp->softc; > + struct g_gsched *gsp = sc->sc_gsched; > + struct bio *bp; > + > + KASSERT(mtx_owned(&sc->sc_mtx), > + ("sc_mtx not owned during forced dispatch")); > + > + while ((bp = gsp->gs_next(sc->sc_data, 1)) != NULL) > + g_io_request(bp, LIST_FIRST(&gp->consumer)); > +} > + > +/* > + * The main dispatch loop, called either here after the start > + * routine, or by scheduling algorithms when they receive a timeout > + * or a 'done' notification. Does not share code with the forced > + * dispatch path, since the gs_done() callback can call us. > + */ > +void > +g_sched_dispatch(struct g_geom *gp) > +{ > + struct g_sched_softc *sc = gp->softc; > + struct g_gsched *gsp = sc->sc_gsched; > + struct bio *bp; > + > + KASSERT(mtx_owned(&sc->sc_mtx), ("sc_mtx not owned during dispatch")); > + > + if ((sc->sc_flags & G_SCHED_FLUSHING)) > + return; > + > + while ((bp = gsp->gs_next(sc->sc_data, 0)) != NULL) > + g_io_request(bp, LIST_FIRST(&gp->consumer)); > +} > + > +/* > + * Recent (8.0 and above) versions of FreeBSD have support to > + * register classifiers of disk requests. The classifier is > + * invoked by g_io_request(), and stores the information into > + * bp->bio_classifier1. > + * > + * Support for older versions, which is left here only for > + * documentation purposes, relies on two hacks: > + * 1. classification info is written into the bio_caller1 > + * field of the topmost node in the bio chain. This field > + * is rarely used, but this module is incompatible with > + * those that use bio_caller1 for other purposes, > + * such as ZFS and gjournal; > + * 2. g_io_request() is patched in-memory when the module is > + * loaded, so that the function calls a classifier as its > + * first thing. g_io_request() is restored when the module > + * is unloaded. This functionality is only supported for > + * x86 and amd64, other architectures need source code changes. > + */ > + > +/* > + * Lookup the identity of the issuer of the original request. > + * In the current implementation we use the curthread of the > + * issuer, but different mechanisms may be implemented later > + * so we do not make assumptions on the return value which for > + * us is just an opaque identifier. > + */ > + > +static inline u_long > +g_sched_classify(struct bio *bp) > +{ > + > +#if __FreeBSD_version > 800098 > + /* we have classifier fields in the struct bio */ > +#define HAVE_BIO_CLASSIFIER > + return ((u_long)bp->bio_classifier1); > +#else > +#warning old version!!! > + while (bp->bio_parent != NULL) > + bp = bp->bio_parent; > + > + return ((u_long)bp->bio_caller1); > +#endif > +} > + > +/* Return the hash chain for the given key. */ > +static inline struct g_hash * > +g_sched_hash(struct g_sched_softc *sc, u_long key) > +{ > + > + return (&sc->sc_hash[key & sc->sc_mask]); > +} > + > +/* > + * Helper function for the children classes, which takes > + * a geom and a bio and returns the private descriptor > + * associated to the request. This involves fetching > + * the classification field and [al]locating the > + * corresponding entry in the hash table. > + */ > +void * > +g_sched_get_class(struct g_geom *gp, struct bio *bp) > +{ > + struct g_sched_softc *sc; > + struct g_sched_class *gsc; > + struct g_gsched *gsp; > + struct g_hash *bucket; > + u_long key; > + > + sc = gp->softc; > + key = g_sched_classify(bp); > + bucket = g_sched_hash(sc, key); > + LIST_FOREACH(gsc, bucket, gsc_clist) { > + if (key == gsc->gsc_key) { > + gsc->gsc_refs++; > + return (gsc->gsc_priv); > + } > + } > + > + gsp = sc->sc_gsched; > + gsc = malloc(sizeof(*gsc) + gsp->gs_priv_size, > + M_GEOM_SCHED, M_NOWAIT | M_ZERO); > + if (!gsc) > + return (NULL); > + > + if (gsp->gs_init_class(sc->sc_data, gsc->gsc_priv)) { > + free(gsc, M_GEOM_SCHED); > + return (NULL); > + } > + > + gsc->gsc_refs = 2; /* 1 for the hash table, 1 for the caller. */ > + gsc->gsc_key = key; > + LIST_INSERT_HEAD(bucket, gsc, gsc_clist); > + > + gsc->gsc_expire = ticks + me.gs_expire_secs * hz; > + > + return (gsc->gsc_priv); > +} > + > +/* > + * Release a reference to the per-client descriptor, > + */ > +void > +g_sched_put_class(struct g_geom *gp, void *priv) > +{ > + struct g_sched_class *gsc; > + struct g_sched_softc *sc; > + > + gsc = g_sched_priv2class(priv); > + gsc->gsc_expire = ticks + me.gs_expire_secs * hz; > + > + if (--gsc->gsc_refs > 0) > + return; > + > + sc = gp->softc; > + sc->sc_gsched->gs_fini_class(sc->sc_data, priv); > + > + LIST_REMOVE(gsc, gsc_clist); > + free(gsc, M_GEOM_SCHED); > +} > + > +static void > +g_sched_hash_fini(struct g_geom *gp, struct g_hash *hp, u_long mask, > + struct g_gsched *gsp, void *data) > +{ > + struct g_sched_class *cp, *cp2; > + int i; > + > + if (!hp) > + return; > + > + if (data && gsp->gs_hash_unref) > + gsp->gs_hash_unref(data); > + > + for (i = 0; i < G_SCHED_HASH_SIZE; i++) { > + LIST_FOREACH_SAFE(cp, &hp[i], gsc_clist, cp2) > + g_sched_put_class(gp, cp->gsc_priv); > + } > + > + hashdestroy(hp, M_GEOM_SCHED, mask); > +} > + > +static struct g_hash * > +g_sched_hash_init(struct g_gsched *gsp, u_long *mask, int flags) > +{ > + struct g_hash *hash; > + > + if (gsp->gs_priv_size == 0) > + return (NULL); > + > + hash = hashinit_flags(G_SCHED_HASH_SIZE, M_GEOM_SCHED, mask, flags); > + > + return (hash); > +} > + > +static void > +g_sched_flush_classes(struct g_geom *gp) > +{ > + struct g_sched_softc *sc; > + struct g_sched_class *cp, *cp2; > + int i; > + > + sc = gp->softc; > + > + if (!sc->sc_hash || ticks - sc->sc_flush_ticks <= 0) > + return; > + > + for (i = 0; i < G_SCHED_HASH_SIZE; i++) { > + LIST_FOREACH_SAFE(cp, &sc->sc_hash[i], gsc_clist, cp2) { > + if (cp->gsc_refs == 1 && ticks - cp->gsc_expire > 0) > + g_sched_put_class(gp, cp->gsc_priv); > + } > + } > + > + sc->sc_flush_ticks = ticks + me.gs_expire_secs * hz; > +} > + > +/* > + * Wait for the completion of any outstanding request. To ensure > + * that this does not take forever the caller has to make sure that > + * no new request enter the scehduler before calling us. > + * > + * Must be called with the gp mutex held and topology locked. > + */ > +static int > +g_sched_wait_pending(struct g_geom *gp) > +{ > + struct g_sched_softc *sc = gp->softc; > + int endticks = ticks + hz; > + > + g_topology_assert(); > + > + while (sc->sc_pending && endticks - ticks >= 0) > + msleep(gp, &sc->sc_mtx, 0, "sched_wait_pending", hz / 4); > + > + return (sc->sc_pending ? ETIMEDOUT : 0); > +} > + > +static int > > *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***