Changeset 565

Show
Ignore:
Timestamp:
02/24/07 07:30:42 (2 years ago)
Author:
hollow
Message:

add capabilities, resource limits and cpu scheduler sections

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved
  • trunk/doc/manual/intro/vserver.tex

    r562 r565  
    292292 
    293293 
     294\section{Features} 
     295 
     296Recent Linux Kernels already provide many security features that are utilized 
     297by Linux-VServer to do its work. Especially features such as the Linux 
     298Capability System, Resource Limits, File Attributes and the Change Root 
     299Environment. The following sections will give a short overview about each of 
     300these and the additional features implemented by the Linux-VServer project. 
     301 
     302 
     303\subsection{Capabilities and Flags} 
     304 
     305A capability is a token used by a process to prove that it is allowed to 
     306perform an operation on an object. The Linux Capability System is based on 
     307"POSIX Capabilities", a somewhat different concept, designed to split up the 
     308all powerful root privilege into a set of distinct privileges. 
     309 
     310\subsubsection{POSIX Capabilities} 
     311 
     312A process has three sets of bitmaps called the inheritable(I), permitted(P), 
     313and effective(E) capabilities. Each capability is implemented as a bit in each 
     314of these bitmaps that is either set or unset. 
     315 
     316When a process tries to do a privileged operation, the operating system will 
     317check the appropriate bit in the effective set of the process (instead of 
     318checking whether the effective uid of the process is 0 as is normally done). 
     319 
     320For example, when a process tries to set the clock, the Linux kernel will check 
     321that the process has the \verb,CAP_SYS_TIME, bit (which is currently bit 25) 
     322set in its effective set. 
     323 
     324The permitted set of the process indicates the capabilities the process can 
     325use. The process can have capabilities set in the permitted set that are not in 
     326the effective set. 
     327 
     328This indicates that the process has temporarily disabled this capability. A 
     329process is allowed to set a bit in its effective set only if it is available in 
     330the permitted set. The distinction between effective and permitted exists so 
     331that processes can "bracket" operations that need privilege. 
     332 
     333The inheritable capabilities are the capabilities of the current process that 
     334should be inherited by a program executed by the current process. The permitted 
     335set of a process is masked against the inheritable set during \verb,exec(),. 
     336Nothing special happens during \verb,fork(), or \verb,clone(),. Child processes 
     337and threads are given an exact copy of the capabilities of the parent process. 
     338 
     339The implementation in Linux stopped at this point, whereas POSIX Capabilities 
     340require the addition of capability sets to files too, to replace the SUID flag 
     341(at least for executables). 
     342 
     343\subsubsection{Upper Bound for Capabilities} 
     344 
     345Because the current Linux Capability system does not implement the filesystem 
     346related portions of POSIX Capabilities which would make setuid and setgid 
     347executables secure, and because it is much safer to have a secure upper bound 
     348for all processes within a context, an additional per-context capability mask 
     349has been added to limit all processes belonging to that context to this mask. 
     350The meaning of the individual caps (bits) of the capability bound mask is 
     351exactly the same as with the permitted capability set.  
     352 
     353\subsubsection{Context Capabilities} 
     354 
     355As the Linux capabilities have almost reached the maximum number that is 
     356possible without heavy modifications to the kernel, it was a natural step to 
     357add a context-specific capability system. 
     358 
     359The Linux-VServer context capability set acts as a mechanism to fine tune 
     360existing Linux capabilities. It is not visible to the processes within a 
     361context, as they would not know how to modify or verify it.  
     362 
     363In general there are two ways to use those capabilities:  
     364 
     365\begin{itemize} 
     366\item Require one or a number of context capabilities to be set in addition to 
     367        a given Linux capability, each one controlling a distinct part of the 
     368        functionality. For example the \verb,CAP_NET_ADMIN, could be split into RAW 
     369        and PACKET sockets, so you could take away each of them separately by not 
     370        providing the required context capability.  
     371 
     372\item Consider the context capability sufficient for a specified functionality, 
     373        even if the Linux Capability says something different. For example mount() 
     374        requires \verb,CAP_SYS_ADMIN, which adds a dozen other things we do not 
     375        want, so we define \verb,VXC_SECURE_MOUNT, to allow mounts for certain 
     376        contexts.  
     377\end{itemize} 
     378 
     379The difference between the context flags and the context capabilities is more 
     380an abstract logical separation than a functional one, because they are handled 
     381very similar. 
     382% TODO: add list of caps/flags to appendix and cross-ref 
     383 
     384 
     385\subsection{Resource Limits} 
     386 
     387Most properties related to system resources, might it be the memory 
     388consumption, the number of processes or file-handles, qualify for imposing 
     389limits on them.  
     390 
     391The Linux kernel provides the \verb,getrlimit, and \verb,setrlimit, system 
     392calls to get and set resource limits per process. Each resource has an 
     393associated soft and hard limit. The soft limit is the value that the kernel 
     394enforces for the corresponding resource. The hard limit acts as a ceiling for 
     395the soft limit: an unprivileged process may only set its soft limit to a value 
     396in the range from 0 up to the hard limit, and (irreversibly) lower its hard 
     397limit. A privileged process (one with the \verb,CAP_SYS_RESOURCE, capability) 
     398may make arbitrary changes to either limit value.  
     399 
     400The Linux-VServer kernel extends this system to provide resource limits for 
     401whole contexts, not just single processes. Additionally a few new limit types 
     402missing in the vanilla kernel were introduced.  
     403 
     404Additionally the context limit system keeps track of observed maxima and 
     405resource limit hits, to provide some feedback for the administrator. 
     406% TODO: add list of limits to appendix and cross-ref 
     407 
     408 
     409\subsection{CPU Scheduler} 
     410 
     411It is important to have a decent understanding of both processes and threads 
     412before learning about schedulers. 
     413 
     414\subsubsection{Programs and Processes} 
     415 
     416A program is a combination of instructions and data put together to perform a 
     417task when executed. A process is an instance of a program (what one might call 
     418a "running" program). An analogy is that programs are like classes in languages 
     419like C++ and Java, and processes are like objects (instantiated instances of 
     420classes). Processes are an abstraction created to embody the state of a program 
     421during its execution. This means keeping track of the data that is associated 
     422with a thread or threads of execution, which includes variables, hardware state 
     423(e.g. registers and the program counter, etc...), and the contents of an 
     424address space. 
     425 
     426\subsubsection{Threads} 
     427 
     428A process can have multiple threads of execution that work together to 
     429accomplish its goals. These threads of execution are aptly named threads. A 
     430kernel must keep track of each thread's stack and hardware state, or whatever 
     431is necessary to track a single flow of execution within a process. Usually 
     432threads share address spaces, but they do not have to (often they merely 
     433overlap). It is important to remember that only one thread may be executing on 
     434a CPU at any given time, which is basically the reason kernels have CPU 
     435schedulers. An example of multiple threads within a process can be found in 
     436most web browsers. Usually at least one thread exists to handle user interface 
     437events (like stopping a page load), one thread exists to handle network 
     438transactions, and one thread exists to render web pages. 
     439 
     440\subsubsection{Scheduling in Linux} 
     441 
     442Multitasking kernels (like Linux) allow more than one process to exist at any 
     443given time, and furthermore each process is allowed to run as if it were the 
     444only process on the system. Processes do not need to be aware of any other 
     445processes unless they are explicitly designed to be. This makes programs easier 
     446to develop, maintain, and port. 
     447 
     448Though each CPU in a system can execute only one thread within a process at a 
     449time, many threads from many processes appear to be executing at the same time. 
     450This is because threads are scheduled to run for very short periods of time and 
     451then other threads are given a chance to run. A kernel's scheduler enforces a 
     452thread scheduling policy, including when, for how long, and in some cases where 
     453(on Symmetric Multiprocessing (SMP) systems) threads can execute. 
     454 
     455Normally the scheduler runs in its own thread, which is woken up by a timer 
     456interrupt. Otherwise it is invoked via a system call or another kernel thread 
     457that wishes to yield the CPU. A thread will be allowed to execute for a certain 
     458amount of time, then a context switch to the scheduler thread will occur, 
     459followed by another context switch to a thread of the scheduler's choice. This 
     460cycle continues, and in this way a certain policy for CPU usage is carried out. 
     461 
     462\subsubsection{Token Bucket Extension} 
     463 
     464While the basic idea of Linux-VServer is a peaceful coexistence of all 
     465contexts, sharing the common resources in a respectful way, it is sometimes 
     466useful to control the resource distribution for resource hungry processes. 
     467 
     468The basic principle of a Token Bucket is not very new. It is given here as an 
     469example for the Hard CPU Limit. The same principle also applies to scheduler 
     470priorities, network bandwidth limitation and resource control in general. 
     471 
     472The Linux-VServer scheduler uses this mechanism in the following way: consider 
     473a bucket of a certain size $S$ which is filled with a specified amount of 
     474tokens $R$ every interval $T$, until the bucket is ``full'' -- excess tokens 
     475are spilled. At each timer tick, a running process (here running means 
     476actually needing the CPU as opposed to ``running'' as in ``existing'') consumes 
     477exactly one token from the bucket, unless the bucket is empty, in which case 
     478the process is put on a hold queue until the bucket has been refilled with a 
     479minimum $M$ of tokens. The process is then rescheduled. 
     480 
     481A major advantage of a Token Bucket is that a certain amount of tokens can be 
     482accumulated in times of quiescence, which later can be used to burst when 
     483resources are required. 
     484 
     485Where a per-process Token Bucket would allow for a CPU resource limitation 
     486of a single process, a Context Token Bucket allows to control the CPU usage 
     487of all confined processes. 
     488 
     489Another approach, which is also implemented, is to use the current fill 
     490level of the bucket to adjust the process priority, thus reducing the 
     491priority of processes belonging to excessive contexts. 
     492 
     493\subsubsection{Hard CPU Limit} 
     494 
     495The simplest configuration is to just give every context an upper bound for 
     496CPU allocation. The important factor is the ratio: 
     497 
     498\begin{center} 
     499$$\frac{R}{T} \cdot 100 = \%\mbox{ CPU allocation}$$ 
     500\end{center} 
     501 
     502Note that this is the proportion of a \emph{single} CPU in the system. So, if 
     503there are four CPUs and a virtual server should get a complete CPU for itself, 
     504then you would set $R=1, T=4$. 
     505 
     506It is advantageous to smooth operation of the algorithm to make the interval as 
     507small as possible (or much smaller than the bucket size). You can in most cases 
     508simplify the fraction, such as changing \nicefrac{30}{100} to \nicefrac{3}{10}. 
     509 
     510\subsubsection{Burst time} 
     511 
     512To penalize processes after a certain amount of \emph{burst time}, i.e. putting 
     513them on the hold queue, you can use the maximum size $S$ of the bucket and the 
     514minimum number of tokens $M$ to \emph{hold} processes. 
     515 
     516Consider a context with a limit of \nicefrac{1}{2} of CPU time, a bucket of 
     51715000 tokens and a minimum of 2500 tokens. Given that the kernel timer runs at 
     5181000Hz processes that have used the CPU for 30 seconds will be put on hold for 
     5195 seconds. The following formula can be used to calculate $S$ and $M$, using 
     520$B$ as burst time and $H$ as hold time: 
     521 
     522\begin{eqnarray*} 
     523M &=& H \cdot \mbox{Hz} \cdot \frac{R}{T}\\ 
     524S &=& B \cdot \mbox{Hz} \cdot \left (1 - \frac{R}{T} \right ) 
     525\end{eqnarray*} 
     526 
     527\subsubsection{Guarantees} 
     528 
     529A guarantee is nearly the same as a pure hard limit, except that you must not 
     530allocate more than 100\% CPU time to all contexts. In other words, if you have 
     531$N$ contexts and give each one a guarantee of more than \nicefrac{1}{N} CPU 
     532time, it would result in more CPU time needed than physically available, which 
     533cannot work out. The important factor here is the sum of all ratios: 
     534 
     535$$\sum_{i=1}^N \frac{R_i}{T_i} \le 1$$ 
     536 
     537 
     538\subsubsection{Fair Share} 
     539 
     540The fair share configuration is similar to guarantees, except that if the CPU 
     541is idle a context can allocate more CPU time than its guarantee/limit. The 
     542scheduler and bucket configuration was extended in Linux-VServer 2.1.1 to allow 
     543fair share scheduling and is also know as \emph{idle time}. 
     544 
     545Consider a configuration with 5 contexts each limited to \nicefrac{1}{5} of CPU 
     546time, where two of these contexts run CPU intensive processes and the rest is 
     547idle. Given that each context may only allocate \nicefrac{1}{5} of CPU time, 
     548\nicefrac{3}{5} of CPU time are wasted since 3 contexts are idle. 
     549 
     550To distribute the wasted CPU time \emph{fair} among contexts that could need it, 
     551you can configure an allocation ratio for \nicefrac{R}{T} during idle times, 
     552namely \nicefrac{$R^2$}{$T^2$}. To calculate the cpu distribution for context $k$ 
     553the following formula is used: 
     554 
     555$$\left ( \frac{C \cdot \frac{R^2_k}{T^2_k}}{\sum_{i=1}^N \frac{R^2_i}{T^2_i}} + 
     556\frac{R_k}{T_k} \right ) \cdot 100 = \%\mbox{ CPU allocation}$$ 
     557 
     558where $C$ is the idle CPU time, \nicefrac{3}{5} in our example. Consider a 
     559\nicefrac{$R^2$}{$T^2$} ratio of \nicefrac{1}{2} for the first guest and 
     560\nicefrac{1}{4} for the second. This would result in: 
     561 
     562$$\left ( \frac{\frac{3}{5} \cdot \frac{1}{2}}{\frac{1}{2} + \frac{1}{4}} + 
     563\frac{1}{5} \right ) \cdot 100 = 60\%\mbox{ CPU allocation for context 1}$$ 
     564 
     565$$\left ( \frac{\frac{3}{5} \cdot \frac{1}{4}}{\frac{1}{2} + \frac{1}{4}} + 
     566\frac{1}{5} \right ) \cdot 100 = 40\%\mbox{ CPU allocation for context 2}$$ 
     567 
     568If the idle time ratio is the same for all contexts, the formula can be 
     569simplified: 
     570 
     571$$\left ( C \cdot \frac{1}{N} + \frac{R_k}{T_k} \right ) \cdot 100 = \%\mbox{ 
     572CPU allocation}$$ 
     573 
     574Therefore, if 3 of the above 5 contexts would run, i.e. \nicefrac{2}{5} of the 
     575CPU are idle, and we have 3 running contexts, it would result in the expted 
     57633\% split: 
     577 
     578$$\left ( \frac{2}{5} \cdot \frac{1}{3} + \frac{1}{5} \right ) \cdot 100 
     579\approx 33\%\mbox{ CPU allocation}$$ 
     580 
     581 
     582\subsection{Virtual Host Information} 
     583 
     584 
     585\subsection{Filesystem Namespace} 
     586 
     587 
     588\subsection{ProcFS Security} 
     589 
     590 
     591\subsection{Chroot Barrier} 
     592 
     593 
     594\subsection{Disk Limits} 
     595 
     596 
     597\subsection{Quotas} 
     598 
     599 
     600\subsection{Copy-on-Write Link Breaking} 
     601 
     602 
     603\subsection{Network Addresses} 
     604 
     605 
    294606% TODO: more info needed here 
    295607\section{History} 
     
    308620 
    309621Additionally, \textbf{Enrico Scholz} decided to reimplement Jack's vserver 
    310 tools in \textbf{C}. These are now distributed as util-vserver. They are 
     622tools in \textbf{C}. These are now distributed as util-vserver. They are 
    311623backward compatible to Jack's tools as far as possible, but follow the kernel 
    312624patch development more closely. 
  • trunk/doc/manual/manual.tex

    r564 r565  
    66 
    77% header and footer 
    8 \usepackage[footexclude,markuppercase]{scrpage2} 
     8\usepackage[footexclude]{scrpage2} 
    99\automark{section} 
    1010\setheadwidth{text} 
     
    1212 
    1313\deftripstyle{vcdmanual}[1pt][.3pt] 
    14         {\pagemark}{}{\MakeUppercase{\headmark}~} 
    15         {}{\small\textsf{This work is licensed under a Creative 
    16         Commons Attribution-NonCommercial-ShareAlike 2.5 License}}{} 
     14{\pagemark}{}{\sc\headmark}{}{\small\it\textsf{This work is licensed under a 
     15Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License}}{} 
    1716 
    1817% code listings 
     
    3938\usepackage{amsfonts} 
    4039\usepackage{amssymb} 
     40\usepackage{nicefrac} 
    4141 
    4242% url and hyperref