Transcript LDD3 11 Notes

Data Types in the Kernel
Ted Baker  Andy Wang
CIS 4930 / COP 5641
Kernel Data Types

For portability


Should compile with –Wall –Wstrictprototypes flags
Three main classes



Standard C types (e.g., int)
Explicitly sized types (e.g., u32)
Types for specific kernel objects (e.g.,
pid_t)
Use of Standard C Types


Normal C types are not the same size
on all architectures
Try misc-progs/database
% misc-progs/datasize
arch Size: char short int long ptr long-long u8 u16 u32 u64
i686
1
2
4
4
4
8
1
2
4
8
Use of Standard C Types

64-bit platforms have different data
type representations
arch Size: char short int long ptr long-long u8 u16 u32 u64
i386
1
2
4
4
4
8
1
2
4
8
alpha
1
2
4
8
8
8
1
2
4
8
armv4l
1
2
4
4
4
8
1
2
4
8
ia64
1
2
4
8
8
8
1
2
4
8
m68k
1
2
4
4
4
8
1
2
4
8
mips
1
2
4
4
4
8
1
2
4
8
ppc
1
2
4
4
4
8
1
2
4
8
sparc
1
2
4
4
4
8
1
2
4
8
sparc64
1
2
4
4
4
8
1
2
4
8
x86_64
1
2
4
8
8
8
1
2
4
8
Use of Standard C Types

Knowing that pointers and long
integers have the same size

Using unsigned long for kernel
addresses prevents unintended pointer
dereferencing
Assigning an Explicit Size to
Data Items

See <asm/types.h>





u8; /* unsigned byte (8-bits) */
u16; /* unsigned word (16-bits) */
u32; /* unsigned 32-bit value */
u64; /* unsigned 64-bit value */
If a user-space program needs to use these
types, use __ prefix (e.g., __u8)
Assigning an Explicit Size to
Data Items

Kernel also uses conventional types,
such as unsigned int

Usually done for backward compatibility
Interface-Specific Types

Interface-specific type: defined by a
library to provide an interface to
specific data structure (e.g., pid_t)
Interface-Specific Types

Many _t types are defined in
<linux/types.h>

Problematic in printk statements

One solution is to cast the value to the
biggest possible type (e.g., unsigned
long)


Avoids warning messages
Will not lose data bits
Other Portability Issues


Be suspicious of explicit constant
values
Most values are parameterized
Timer Intervals

Do not assume 1000 jiffies per second

Scale times using HZ (number of
interrupts per second)


For example, check against a timeout of half
a second, compare the elapsed time against
HZ/2
Number of jiffies corresponding to msec
second is always msec*HZ/1000
Page Size

Memory page is PAGE_SIZE bytes,
not 4KB




Can vary from 4KB to 64KB
PAGE_SHIFT contains the number of bits
to shift an address to get its page number
See <asm/page.h>
User-space program can use
getpagesize library function
Page Size

Example

To allocate 16KB

Should not specify an order of 2 to
get_free_pages
Use get_order

#include <asm/page.h>
int order = get_order(16*1024);
buf = get_free_pages(GFP_KERNEL, order);
Byte Order



PC stores multibyte values low-byte
first (little-endian)
Some platforms use big-endian
Use predefined macros


<linux/byteorder/big_endian.h>
<linux/byteorder/little_endian.h>
Byte Order

Examples

u32 cpu_to_le32(u32);



u64 be64_to_cpu(u64);


cpu = internal CPU representation
le = little endian
be = big endian
U16 cpu_to_le16p(u16);

p = pointer
Data Alignment

How to read a 4-byte value stored at
an address that is not a multiple of 4
bytes?


i386 permits this kind of access
Not all architectures permit it

Can raise exceptions
Data Alignment

Use the following typeless macros



#include <asm/unaligned.h>
get_unaligned(ptr);
put_unaligned(val, ptr);
Data Alignment

Another issue is the portability of data
structures


Compiler rearranges structure fields to be
aligned according to platform-specific
conventions
Automatically add padding to make
things aligned

May no longer match the intended format
Data Alignment

Use natural alignment


8-byte items go in an address multiple of
8
Use filler fields that avoid leaving holes in
the data structure


Not all platforms align 64-bit values on 64-bit
boundaries
Might waste memory
Data Alignment


Tell the compiler to pack the data
structure with no fillers added
Example: <linux/edd.h>
struct {
u16 id;
u64 lun;
u16 reserved1;
u32 reserved2;
} __attribute__ ((packed)) scsi;
Without __attribute__
((packed)), lun would be
preceded by 2-6 bytes of
fillers
Data Alignment

No compiler
optimizations

Some compiler
optimizations

__attribute__
((packed))
Pointers and Error Values

Functions that return pointers cannot
report negative error values


Return NULL on failure
Some kernel interfaces encode error
code in a pointer value

Cannot be compared against NULL

To use this feature, include
<linux/err.h>
Pointers and Error Values

To return an error, use


To test whether a returned pointer is
an error code, use


void *ERR_PTR(long error);
long IS_ERR(const void *ptr);
To access the error code, use

long PTR_ERR(const void *ptr);
Linked Lists

Linux provides a standard
implementation of circular, doubly
linked lists


List functions perform no locking
To use the list mechanism, include
<linux/list.h>, which contains
struct list_head {
struct list_head *next, *prev;
};
Linked Lists

To use the Linux list facility

Need to embed a list_head in the
structures that make up the list
struct todo_struct
struct list_head
int priority; /*
/* ... add other
};
{
list;
driver specific */
driver-specific fields */
Linked Lists
More Fun with Linked Lists
C
2
A
3
list_head sorted_by_char
list_head sorted_by_num
What if a structure owns
its own list?
B
1
Can
allocate list
elements
as an array
Linked Lists


The head of the list is usually a
standalone structure
To declare and initialize a list head, call
struct list_head todo_list;
INIT_LIST_HEAD(&todo_list);

To initialize at compile time, call
LIST_HEAD(todo_list);
Linked Lists

See <linux/list.h> for a list of list
functions
/* add the new entry after the list head */
/* use it to build stacks */
list_add(struct list_head *new, struct list_head *head);
/* add the new entry before the list head (tail) */
/* use it to build FIFO queues */
list_add_tail(struct list_head *new, struct list_head *head);
Linked Lists
/* the given entry is removed from the list */
/* if the entry might be reinserted into another list, call
list_del_init */
list_del(struct list_head *entry);
list_del_init(struct list_head *entry);
/* remove the entry from one list and insert into another
list */
list_move(struct list_head *entry, struct list_head *head);
list_move_tail(struct list_head *entry,
struct list_head *head);
/* return a nonzero value if the given list is empty */
list_empty(struct list_head *head);
Linked Lists
/* insert a list immediately after head */
list_splice(struct list_head *list, struct list_head *head);

To access the data structure itself, use
list_entry(struct list_head *ptr, type_of_struct,
field_name);


Same as container_of()
ptr is a pointer to a struct
list_head entry
Linked Lists

type_of_struct is the type of the
structure containing the ptr

field_name is the name of the list field
within the structure
Example

struct todo_struct *todo_ptr
= list_entry(listptr, struct todo_struct, list);
#define container_of(ptr, type, member) ({
const typeof(((type *)0->member) *__mptr = (ptr);
Type
(type *) ((char *)__mptr – offsetof(type, member)); })
checking
Linked Lists

To traverse the linked list, one can
follow the prev and next pointers
void todo_add_entry(struct todo_struct *new) {
struct list_head *ptr;
struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list;
ptr = ptr->next) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
Linked Lists

One can also use predefined macros
void todo_add_entry(struct todo_struct *new) {
struct list_head *ptr;
struct todo_struct *entry;
list_for_each(ptr, &todo_list) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
Linked Lists

Predefined macros avoid simple
programming errors

See <linux/list.h>
/* creates a loop that executes once with cursor pointing at
each successive entry */
/* be careful about changing the list while iterating */
list_for_each(struct list_head *cursor,
struct list_head *list)
/* iterates backward */
list_for_each_prev(struct list_head *cursor,
struct list_head *list)
Linked Lists
/* for deleting entries in the list
/* stores the next entry in next at
*/
list_for_each_safe(struct list_head
struct list_head
struct list_head
*/
the beginning of the loop
*cursor,
*next,
*list)
/* ease the process of dealing with a list containing a given
type */
/* no need to call list_entry inside the loop */
list_for_each_entry(type *cursor, struct list_head *list,
member)
list_for_each_entry_safe(type *cursor, type *next,
struct list_head *list, member)