Porting semaphore.h from Linux to T-Kernel
Written by: Neil Han (PKU)
1. Semaphores and Mutexes in Linux Device Drivers:
Our goal is to make our operations on the scull data structure atomic, meaning that the entire operation happens at once as far as other threads of execution are concerned.
When semaphores are used for mutual exclusion—keeping multiple processes from running within a critical section simultaneously—their value will be initially set to 1. Such a semaphore can be held only by a single process or thread at any given time. A semaphore used in this mode is sometimes called a mutex, which is, of course, an abbreviation for "mutual exclusion." Almost all semaphores found in the Linux kernel are used for mutual exclusion.
·The Linux Semaphore Implementation:
To use semaphores, kernel code must include <asm/semaphore.h>. The relevant type is struct semaphore; actual semaphores can be declared and initialized in a few ways. One is to create a semaphore directly, then set it up with sema_init:
void sema_init(struct semaphore *sem, int val)
where val is the initial value to assign to a semaphore.
Usually, however, semaphores are used in a mutex mode. To make this common case a little easier, the kernel has provided a set of helper functions and macros. Thus, a mutex can be declared and initialized with one of the following:
DECLARE_MUTEX(name);
DECLARE_MUTEX_LOCKED(name);
Here, the result is a semaphore variable (called name) that is initialized to 1 (with DECLARE_MUTEX) or 0 (with DECLARE_MUTEX_LOCKED). In the latter case, the mutex starts out in a locked state; it will have to be explicitly unlocked before any thread will be allowed access.
If the mutex must be initialized at runtime (which is the case if it is allocated dynamically, for example), use one of the following:
void init_MUTEX(struct semaphore *sem);
void init_MUTEX_LOCKED(struct semaphore *sem);
In the Linux world, the P function is called down—or some variation of that name. Here, "down" refers to the fact that the function decrements the value of the semaphore and, perhaps after putting the caller to sleep for a while to wait for the semaphore to become available, grants access to the protected resources. There are three versions of down:
void down(struct semaphore *sem);
int down_interruptible(struct semaphore *sem);
int down_trylock(struct semaphore *sem);
down decrements the value of the semaphore and waits as long as need be. down_interruptible does the same, but the operation is interruptible. The interruptible version is almost always the one you will want; it allows a user-space process that is waiting on a semaphore to be interrupted by the user. You do not, as a general rule, want to use noninterruptible operations unless there truly is no alternative. Non-interruptible operations are a good way to create unkillable processes (the dreaded "D state" seen in ps), and annoy your users. Using down_interruptible requires some extra care, however, if the operation is interrupted, the function returns a nonzero value, and the caller does not hold the semaphore. Proper use of down_interruptible requires always checking the return value and responding accordingly.
The final version (down_trylock) never sleeps; if the semaphore is not available at the time of the call, down_trylock returns immediately with a nonzero return value.
The Linux equivalent to V is up:
void up(struct semaphore *sem);
As you would expect, any thread that takes out a semaphore is required to release it with one (and only one) call to up. Special care is often required in error paths; if an error is encountered while a semaphore is held, that semaphore must be released before returning the error status to the caller. Failure to free a semaphore is an easy error to make; the result (processes hanging in seemingly unrelated places) can be hard to reproduce and track down.
2. Corresponding part functions provided by T-Kernel:
A semaphore is an object identified by an ID number called a semaphore ID.
A semaphore contains a resource count indicating whether the corresponding resource exists and in what quantity, and a queue of tasks waiting to acquire the resource. When a task (the task making event notification) returns m resources, it increments the semaphore resource count by m. When a task (the task waiting for an event) acquires n resources, it decreases the semaphore resource count by n. If the number of semaphore resources is insufficient (i.e., further reducing the semaphore resource count would cause it to go into negative territory), a task attempting to acquire resources goes into WAIT state until the next time resources are returned. A task waiting for semaphore resources is put in the semaphore queue.
To prevent too many resources from being returned to a semaphore, a maximum resource count can be set for each semaphore. Error is reported if it is attempted to return resources to a semaphore that would cause this maximum count to be exceeded.
·T-Kernel Functions:
2.1 ID semid = tk_cre_sem ( T_CSEM *pk_csem ) ;
[Parameters]
T CSEM* pk csem Information about the semaphore to be created
pk_csem detail:
VP exinf Extended information
ATR sematr Semaphore attributes
INT isemcnt Initial semaphore count
INT maxsem Maximum semaphore count
[Return Parameters]
ID semid Semaphore ID
or Error Code
[Error Codes]…
[Description]
Creates a semaphore, assigning to it a semaphore ID.
This system call allocates a control block to the created semaphore, setting the initial count to isemcnt and maximum count (upper limit) to maxsem. It must be possible to set maxsem to at least 65535.
Whether values above 65536 can be set is implementation-dependent.
exinf can be used freely by the user to set miscellaneous information about the created semaphore.
The information set in this parameter can be referenced by tk_ref_sem. If a larger area is needed for indicating user information, or if the information may need to be changed after the semaphore is created, this can be done by allocating separate memory for this purpose and putting the memory packet address in exinf. The OS pays no attention to the contents of exinf.
sematr indicates system attributes in its low bits and implementation-dependent information in the
high bits. Designation in the system attributes part of sematr is as follows.
sematr:= (TA_TFIFO || TA_TPRI) | (TA_FIRST || TA_CNT) | [TA_NODISWAI]
TA_TFIFO Tasks are queued in FIFO order
TA_TPRI Tasks are queued in priority order
TA_FIRST The first task in the queue has precedence
TA_CNT Tasks with fewer requests have precedence
TA_NODISWAI Wait disabling by tk_dis_wai is prohibited
2.2 ER ercd = tk_del_sem ( ID semid ) ;
[Return Parameters]
ER ercd Error code
[Description]
Deletes the semaphore designated in semid.
The semaphore ID and control block area are released as a result of this system call.
This system call completes normally even if there is a task waiting for condition fulfillment in the semaphore, but error code E_DLT is returned to the task in WAIT state.
2.3 ER ercd = tk_sig_sem ( ID semid, INT cnt ) ; Like V operation
[Parameters]
ID semid Semaphore ID
INT cnt Resource return count
[Description]
Returns to the semaphore designated in semid the number of resources indicated in cnt.
2.4 ER ercd = tk_wai_sem ( ID semid, INT cnt, TMO tmout ) ; Like P operation
[Parameters]
ID semid Semaphore ID
INT cnt Resource request count
TMO tmout Timeout designation
[Description]
Gets from the semaphore designated in semid the number of resources indicated in cnt. If the requested resources can be allocated, the task issuing this system call does not enter WAIT state but continues executing. In this case the semaphore count (semcnt) is decreased by the size of cnt. If the resources are not available, the task issuing this system call enters WAIT state, and is put in the queue of tasks waiting for the semaphore. The semaphore count (semcnt) for this semaphore does not change in this case.
A maximum wait time (timeout) can be set in tmout. If the tmout time elapses before the wait release condition is met (tk_sig_sem is not executed), the system call terminates, returning timeout error code E_TMOUT.
Only positive values can be set in tmout. The time base for tmout (time unit) is the same as that for system time (= 1 ms).
When TMO_POL = 0 is set in tmout, this means 0 was designated as the timeout value, and E TMOUT is returned without entering WAIT state even if no resources are acquired.
When TMO_FEVR = (-1) is set in tmout, this means infinity was designated as the timeout value, and the task continues to wait for resource acquisition without timing out.
2.5 ER ercd = tk_ref_sem ( ID semid, T_RSEM *pk_rsem ) ;
[Parameters]
ID semid Semaphore ID
T RSEM* pk rsem Address of packet for returning status information
pk rsem detail:
VP exinf Extended information
ID wtsk Waiting task information
INT semcnt Semaphore count
[Description]
References the status of the semaphore designated in semid, passing in the return parameters the current semaphore count (semcnt), information on tasks waiting for the semaphore (wtsk), and extended information (exinf).
wtsk indicates the ID of a task waiting for the semaphore. If there are two or more such tasks, the ID of the task at the head of the queue is returned. If there are no waiting tasks, wtsk = 0 is returned.
If the designated semaphore does not exist, error code E_NOEXS is returned.
3. Porting
Only functions init_MUTEX, DECLARE_MUTEX, DECLARE_MUTEX_LOCKED, init_MUTEX_LOCKED, down and up are invoked, so they are ported like the followings.
3.1 Definition:
In Linux semaphore is defined as:
struct semaphore {
atomic_t count;
int sleepers;
wait_queue_head_t wait;
#if WAITQUEUE_DEBUG
long __magic;
#endif
};
In T-Kernel, however, the semaphore is looked up by ID. Because there is not a mechanism to substitute struct semaphore for ID, I have to handle like the following: (If anyone knows how to substitute, pls email me (anec@pub.ss.pku.edu.cn), I’ll be really appreciated)
struct semaphore {
ID tsem;
};
3.2 init_MUTEX:
static inline void init_MUTEX (struct semaphore *sem)
{
T_CSEM tcsem;
tcsem.exinf = (VP)0x00000000;
tcsem.sematr = TA_TFIFO | TA_FIRST;
tcsem.isemcnt = 1;
tcsem.maxsem = 1;
sem->tsem = tk_cre_sem(&tcsem);
if (sem->tsem < E_OK)
exit -1;
}
Because Linux semaphore is a structure, there is not initialization failure, but in T-Kernel, it is dynamically allocated, so if failed, it need to exit.
3.3 DECLARE_MUTEX, DECLARE_MUTEX_LOCKED:
static inline struct semaphore SEMAPHORE_INITIALIZER(struct semaphore sem, int count){
T_CSEM tcsem;
tcsem.exinf = (VP)0x00000000;
tcsem.sematr = TA_TFIFO | TA_FIRST;
tcsem.isemcnt = count;
tcsem.maxsem = 1;
sem.tsem = tk_cre_sem(&tcsem);
if (sem.tsem < E_OK)
exit (-1);
return sem;
}
#define __DECLARE_SEMAPHORE_GENERIC(name,count) \
struct semaphore name = SEMAPHORE_INITIALIZER(name,count)
#define DECLARE_MUTEX(name) __DECLARE_SEMAPHORE_GENERIC(name,1)
#define DECLARE_MUTEX_LOCKED(name) __DECLARE_SEMAPHORE_GENERIC(name,0)
3.4 init_MUTEX_LOCKED
static inline void init_MUTEX_LOCKED (struct semaphore *sem)
{
T_CSEM tcsem;
tcsem.exinf = (VP)0x00000000;
tcsem.sematr = TA_TFIFO | TA_FIRST;
tcsem.isemcnt = 0;
tcsem.maxsem = 1;
sem->tsem = tk_cre_sem(&tcsem);
if (sem->tsem < E_OK)
exit -1;
}
3.5 down and up
static inline void down(struct semaphore * sem)
{
tk_wai_sem(sem->tsem, 1, TMO_FEVR); /* wait forever */
}
static inline void up(struct semaphore * sem)
{
tk_sig_sem(sem->tsem, 1);
}
3.6 Information useful in the future: [TKSpec02a]
Memory Allocation Libraries
Since system memory is allocated in block units, libraries are provided for dividing up those blocks for use.
² void* Vmalloc( size_t size )
² void* Vcalloc( size_t nmemb, size_t size )
² void* Vrealloc( void *ptr, size_t size )
² void Vfree( void *ptr )
² void* Kmalloc( size_t size ) /*Frequently used!*/
² void* Kcalloc( size_t nmemb, size_t size )
² void* Krealloc( void *ptr, size_t size )
² void Kfree( void *ptr )
The functions are equivalent to the standard C libraries malloc, calloc, realloc, free and so on. V— means the function is for nonresident memory and K— for resident memory; in both cases the memory is assigned to the TSVCLimit protection level. (note: On T-Kernel, we specify the task protection level that can call up a system call by means of the "TSVCLimit" of the system configuration information. For example, if we specify the TSVCLimit at Level 1, then it becomes impossible to utilize T-Kernel system calls from tasks of protection level 2 and protection level 3. Table 3 supposes TSVCLimit=1. [MMG04a])
These functions cannot be called from a task-independent portion or while dispatching or interrupts are disabled. The behavior if they are called in those situations is undefined. (System failure is a possibility.)
What is the different between resident and non-resident memory?
A No MMU basically all memory is resident. Memory pool creation is pointed to at resident memory area. There is some Memory Allocation Libraries available for allocating memory for non-resident memory.
4. Notes:
4.1 Delete semaphore:
Since there is no corresponding call to delete semaphore, which Linux kernel manage, so must add tk_del_sem in usb_deregister.
All the above mechanisms are validated in VC, but need to be validated in T-Kernel when the project linked.
References:
[MMG04a] “Middleware Migration Guide from ITRON to T-Kernel”, 2004, http://tronweb.super-nova.co.jp/itron-t-kernel-migration1.00.html
[TKSpec02a] “T-Kernel Specification” T-Kernel 1.B0.01 (Aug.2002). This specification describes the mechanism of T-Kernel and defines interfaces for which T-Kernel provide.
[LuxDevD06a] “Linux Device Drivers (3rd edition)”, Alessanddro rubini & Jonathan Corbet, 2006.
[TKSemCode04a] “T-Kernel/OS API demonstration for semaphore”, 2004, http://www.t-engine.com.sg/download.aspx?catid=13&contentid=83, The source code is To demonstrate the use of semaphore as an object indicating the availability of a resource and its quantity as a numerical value.
Note:
If you find any information to be incorrect, please inform me by emailing anec@pub.ss.pku.edu.cn.
Copyright © 2006 Neil Han