String Conversions¶

unsigned long longsimple_strtoull(const char * cp, char ** endp, unsigned int base)¶

convert a string to an unsigned long long

Parameters

constchar*cp

The start of the string

char**endp

A pointer to the end of the parsed string will be placed here

unsignedintbase

The number base to use

Description

This function has caveats. Please use kstrtoull instead.

unsigned longsimple_strtoul(const char * cp, char ** endp, unsigned int base)¶

convert a string to an unsigned long

Parameters

constchar*cp

The start of the string

char**endp

A pointer to the end of the parsed string will be placed here

unsignedintbase

The number base to use

Description

This function has caveats. Please use kstrtoul instead.

longsimple_strtol(const char * cp, char ** endp, unsigned int base)¶

convert a string to a signed long

Parameters

constchar*cp

The start of the string

char**endp

A pointer to the end of the parsed string will be placed here

unsignedintbase

The number base to use

Description

This function has caveats. Please use kstrtol instead.

long longsimple_strtoll(const char * cp, char ** endp, unsigned int base)¶

convert a string to a signed long long

Parameters

constchar*cp

The start of the string

char**endp

A pointer to the end of the parsed string will be placed here

unsignedintbase

The number base to use

Description

This function has caveats. Please use kstrtoll instead.

intvsnprintf(char * buf, size_t size, const char * fmt, va_list args)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

size_tsize

The size of the buffer, including the trailing null space

constchar*fmt

The format string to use

va_listargs

Arguments for the format string

Description

This function generally follows C99 vsnprintf, but has someextensions and a few limitations:

• ``n`` is unsupported
• ``p``* is handled by pointer()

See pointer() or Documentation/core-api/printk-formats.rst for moreextensive description.

Please update the documentation in both places when making changes

The return value is the number of characters which wouldbe generated for the given input, excluding the trailing‘0’, as per ISO C99. If you want to have the exactnumber of characters written intobuf as return value(not including the trailing ‘0’), usevscnprintf(). If thereturn is greater than or equal tosize, the resultingstring is truncated.

If you’re not already dealing with a va_list consider usingsnprintf().

intvscnprintf(char * buf, size_t size, const char * fmt, va_list args)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

size_tsize

The size of the buffer, including the trailing null space

constchar*fmt

The format string to use

va_listargs

Arguments for the format string

Description

The return value is the number of characters which have been written intothebuf not including the trailing ‘0’. Ifsize is == 0 the functionreturns 0.

If you’re not already dealing with a va_list consider usingscnprintf().

See thevsnprintf() documentation for format string extensions over C99.

intsnprintf(char * buf, size_t size, const char * fmt, ...)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

size_tsize

The size of the buffer, including the trailing null space

constchar*fmt

The format string to use

...

Arguments for the format string

Description

The return value is the number of characters which would begenerated for the given input, excluding the trailing null,as per ISO C99. If the return is greater than or equal tosize, the resulting string is truncated.

See thevsnprintf() documentation for format string extensions over C99.

intscnprintf(char * buf, size_t size, const char * fmt, ...)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

size_tsize

The size of the buffer, including the trailing null space

constchar*fmt

The format string to use

...

Arguments for the format string

Description

The return value is the number of characters written intobuf not includingthe trailing ‘0’. Ifsize is == 0 the function returns 0.

intvsprintf(char * buf, const char * fmt, va_list args)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

constchar*fmt

The format string to use

va_listargs

Arguments for the format string

Description

The function returns the number of characters writtenintobuf. Usevsnprintf() orvscnprintf() in order to avoidbuffer overflows.

If you’re not already dealing with a va_list consider usingsprintf().

See thevsnprintf() documentation for format string extensions over C99.

intsprintf(char * buf, const char * fmt, ...)¶

Format a string and place it in a buffer

Parameters

char*buf

The buffer to place the result into

constchar*fmt

The format string to use

...

Arguments for the format string

Description

The function returns the number of characters writtenintobuf. Usesnprintf() orscnprintf() in order to avoidbuffer overflows.

See thevsnprintf() documentation for format string extensions over C99.

intvbin_printf(u32 * bin_buf, size_t size, const char * fmt, va_list args)¶

Parse a format string and place args’ binary value in a buffer

Parameters

u32*bin_buf

The buffer to place args’ binary value

size_tsize

The size of the buffer(by words(32bits), not characters)

constchar*fmt

The format string to use

va_listargs

Arguments for the format string

Description

The format follows C99 vsnprintf, exceptn is ignored, and its argumentis skipped.

The return value is the number of words(32bits) which would be generated forthe given input.

NOTE

If the return value is greater thansize, the resulting bin_buf is NOTvalid forbstr_printf().

intbstr_printf(char * buf, size_t size, const char * fmt, const u32 * bin_buf)¶

Format a string from binary arguments and place it in a buffer

Parameters

char*buf

The buffer to place the result into

size_tsize

The size of the buffer, including the trailing null space

constchar*fmt

The format string to use

constu32*bin_buf

Binary arguments for the format string

Description

This function like C99 vsnprintf, but the difference is that vsnprintf getsarguments from stack, and bstr_printf gets arguments frombin_buf which isa binary buffer that generated by vbin_printf.

The format follows C99 vsnprintf, but has some extensions:

see vsnprintf comment for details.

The return value is the number of characters which wouldbe generated for the given input, excluding the trailing‘0’, as per ISO C99. If you want to have the exactnumber of characters written intobuf as return value(not including the trailing ‘0’), usevscnprintf(). If thereturn is greater than or equal tosize, the resultingstring is truncated.

intbprintf(u32 * bin_buf, size_t size, const char * fmt, ...)¶

Parse a format string and place args’ binary value in a buffer

Parameters

u32*bin_buf

The buffer to place args’ binary value

size_tsize

The size of the buffer(by words(32bits), not characters)

constchar*fmt

The format string to use

...

Arguments for the format string

Description

The function returns the number of words(u32) writtenintobin_buf.

intvsscanf(const char * buf, const char * fmt, va_list args)¶

Unformat a buffer into a list of arguments

Parameters

constchar*buf

input buffer

constchar*fmt

format of buffer

va_listargs

arguments

intsscanf(const char * buf, const char * fmt, ...)¶

Unformat a buffer into a list of arguments

Parameters

constchar*buf

input buffer

constchar*fmt

formatting of buffer

...

resulting arguments

intkstrtol(const char * s, unsigned int base, long * res)¶

convert a string to a long

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign or a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

long*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtol(). Return code must be checked.

intkstrtoul(const char * s, unsigned int base, unsigned long * res)¶

convert a string to an unsigned long

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign, but not a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

unsignedlong*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtoul(). Return code must be checked.

intkstrtoull(const char * s, unsigned int base, unsigned long long * res)¶

convert a string to an unsigned long long

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign, but not a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

unsignedlonglong*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtoull(). Return code must be checked.

intkstrtoll(const char * s, unsigned int base, long long * res)¶

convert a string to a long long

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign or a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

longlong*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtoll(). Return code must be checked.

intkstrtouint(const char * s, unsigned int base, unsigned int * res)¶

convert a string to an unsigned int

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign, but not a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

unsignedint*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtoul(). Return code must be checked.

intkstrtoint(const char * s, unsigned int base, int * res)¶

convert a string to an int

Parameters

constchar*s

The start of the string. The string must be null-terminated, and may alsoinclude a single newline before its terminating null. The first charactermay also be a plus sign or a minus sign.

unsignedintbase

The number base to use. The maximum supported base is 16. If base isgiven as 0, then the base of the string is automatically detected with theconventional semantics - If it begins with 0x the number will be parsed as ahexadecimal (case insensitive), if it otherwise begins with 0, it will beparsed as an octal number. Otherwise it will be parsed as a decimal.

int*res

Where to write the result of the conversion on success.

Description

Returns 0 on success, -ERANGE on overflow and -EINVAL on parsing error.Preferred oversimple_strtol(). Return code must be checked.

intkstrtobool(const char * s, bool * res)¶

convert common user inputs into boolean values

Parameters

constchar*s

input string

bool*res

result

Description

This routine returns 0 iff the first character is one of ‘Yy1Nn0’, or[oO][NnFf] for “on” and “off”. Otherwise it will return -EINVAL. Valuepointed to by res is updated upon finding a match.

voidstring_get_size(u64 size, u64 blk_size, const enum string_size_units units, char * buf, int len)¶

get the size in the specified units

Parameters

u64size

The size to be converted in blocks

u64blk_size

Size of the block (use 1 for size in bytes)

constenumstring_size_unitsunits

units to use (powers of 1000 or 1024)

char*buf

buffer to format to

intlen

length of buffer

Description

This function returns a string formatted to 3 significant figuresgiving the size in the required units.buf should have room forat least 9 bytes and will always be zero terminated.

intstring_unescape(char * src, char * dst, size_t size, unsigned int flags)¶

unquote characters in the given string

Parameters

char*src

source buffer (escaped)

char*dst

destination buffer (unescaped)

size_tsize

size of the destination buffer (0 to unlimit)

unsignedintflags

combination of the flags.

Description

The function unquotes characters in the given string.

Because the size of the output will be the same as or less than the size ofthe input, the transformation may be performed in place.

Caller must provide valid source and destination pointers. Be aware thatdestination buffer will always be NULL-terminated. Source string must beNULL-terminated as well. The supported flags are:

UNESCAPE_SPACE:        '\f' - form feed        '\n' - new line        '\r' - carriage return        '\t' - horizontal tab        '\v' - vertical tabUNESCAPE_OCTAL:        '\NNN' - byte with octal value NNN (1 to 3 digits)UNESCAPE_HEX:        '\xHH' - byte with hexadecimal value HH (1 to 2 digits)UNESCAPE_SPECIAL:        '\"' - double quote        '\\' - backslash        '\a' - alert (BEL)        '\e' - escapeUNESCAPE_ANY:        all previous together

Return

The amount of the characters processed to the destination buffer excludingtrailing ‘0’ is returned.

intstring_escape_mem(const char * src, size_t isz, char * dst, size_t osz, unsigned int flags, const char * only)¶

quote characters in the given memory buffer

Parameters

constchar*src

source buffer (unescaped)

size_tisz

source buffer size

char*dst

destination buffer (escaped)

size_tosz

destination buffer size

unsignedintflags

combination of the flags

constchar*only

NULL-terminated string containing characters used to limitthe selected escape class. If characters are included inonlythat would not normally be escaped by the classes selectedinflags, they will be copied todst unescaped.

Description

The process of escaping byte buffer includes several parts. They are appliedin the following sequence.

1. The character is matched to the printable class, if asked, and incase of match it passes through to the output.
2. The character is not matched to the one fromonly string and thusmust go as-is to the output.
3. The character is checked if it falls into the class given byflags.ESCAPE_OCTAL andESCAPE_HEX are going last since they cover anycharacter. Note that they actually can’t go together, otherwiseESCAPE_HEX will be ignored.

Caller must provide valid source and destination pointers. Be aware thatdestination buffer will not be NULL-terminated, thus caller have to appendit if needs. The supported flags are:

%ESCAPE_SPACE: (special white space, not space itself)        '\f' - form feed        '\n' - new line        '\r' - carriage return        '\t' - horizontal tab        '\v' - vertical tab%ESCAPE_SPECIAL:        '\\' - backslash        '\a' - alert (BEL)        '\e' - escape%ESCAPE_NULL:        '\0' - null%ESCAPE_OCTAL:        '\NNN' - byte with octal value NNN (3 digits)%ESCAPE_ANY:        all previous together%ESCAPE_NP:        escape only non-printable characters (checked by isprint)%ESCAPE_ANY_NP:        all previous together%ESCAPE_HEX:        '\xHH' - byte with hexadecimal value HH (2 digits)

Return

The total size of the escaped output that would be generated forthe given input and flags. To check whether the output wastruncated, compare the return value to osz. There is room left indst for a ‘0’ terminator if and only if ret < osz.

String Manipulation¶

intstrncasecmp(const char * s1, const char * s2, size_t len)¶

Case insensitive, length-limited string comparison

Parameters

constchar*s1

One string

constchar*s2

The other string

size_tlen

the maximum number of characters to compare

char *strcpy(char * dest, const char * src)¶

Copy aNUL terminated string

Parameters

char*dest

Where to copy the string to

constchar*src

Where to copy the string from

char *strncpy(char * dest, const char * src, size_t count)¶

Copy a length-limited, C-string

Parameters

char*dest

Where to copy the string to

constchar*src

Where to copy the string from

size_tcount

The maximum number of bytes to copy

Description

The result is notNUL-terminated if the source exceedscount bytes.

In the case where the length ofsrc is less than that ofcount, the remainder ofdest will be padded withNUL.

size_tstrlcpy(char * dest, const char * src, size_t size)¶

Copy a C-string into a sized buffer

Parameters

char*dest

Where to copy the string to

constchar*src

Where to copy the string from

size_tsize

size of destination buffer

Description

Compatible with*BSD: the result is always a validNUL-terminated string that fits in the buffer (unless,of course, the buffer size is zero). It does not padout the result likestrncpy() does.

ssize_tstrscpy(char * dest, const char * src, size_t count)¶

Copy a C-string into a sized buffer

Parameters

char*dest

Where to copy the string to

constchar*src

Where to copy the string from

size_tcount

Size of destination buffer

Description

Copy the string, or as much of it as fits, into the dest buffer. Thebehavior is undefined if the string buffers overlap. The destinationbuffer is always NUL terminated, unless it’s zero-sized.

Preferred tostrlcpy() since the API doesn’t require reading memoryfrom the src string beyond the specified “count” bytes, and sincethe return value is easier to error-check thanstrlcpy()’s.In addition, the implementation is robust to the string changing outfrom underneath it, unlike the currentstrlcpy() implementation.

Preferred tostrncpy() since it always returns a valid string, anddoesn’t unnecessarily force the tail of the destination buffer to bezeroed. If zeroing is desired please usestrscpy_pad().

Return

• The number of characters copied (not including the trailingNUL)
• -E2BIG if count is 0 orsrc was truncated.

ssize_tstrscpy_pad(char * dest, const char * src, size_t count)¶

Copy a C-string into a sized buffer

Parameters

char*dest

Where to copy the string to

constchar*src

Where to copy the string from

size_tcount

Size of destination buffer

Description

Copy the string, or as much of it as fits, into the dest buffer. Thebehavior is undefined if the string buffers overlap. The destinationbuffer is alwaysNUL terminated, unless it’s zero-sized.

If the source string is shorter than the destination buffer, zerosthe tail of the destination buffer.

For full explanation of why you may want to consider using the‘strscpy’ functions please see the function docstring forstrscpy().

Return

• The number of characters copied (not including the trailingNUL)
• -E2BIG if count is 0 orsrc was truncated.

char *stpcpy(char *__restrict__ dest, const char *__restrict__ src)¶

copy a string from src to dest returning a pointer to the new end of dest, including src’sNUL-terminator. May overrun dest.

Parameters

char*__restrict__dest

pointer to end of string being copied into. Must be large enoughto receive copy.

constchar*__restrict__src

pointer to the beginning of string being copied from. Must not overlapdest.

Description

stpcpy differs from strcpy in a key way: the return value is a pointerto the newNUL-terminating character indest. (For strcpy, the returnvalue is a pointer to the start ofdest). This interface is consideredunsafe as it doesn’t perform bounds checking of the inputs. As such it’snot recommended for usage. Instead, its definition is provided in casethe compiler lowers other libcalls to stpcpy.

char *strcat(char * dest, const char * src)¶

Append oneNUL-terminated string to another

Parameters

char*dest

The string to be appended to

constchar*src

The string to append to it

char *strncat(char * dest, const char * src, size_t count)¶

Append a length-limited, C-string to another

Parameters

char*dest

The string to be appended to

constchar*src

The string to append to it

size_tcount

The maximum numbers of bytes to copy

Description

Note that in contrast tostrncpy(),strncat() ensures the result isterminated.

size_tstrlcat(char * dest, const char * src, size_t count)¶

Append a length-limited, C-string to another

Parameters

char*dest

The string to be appended to

constchar*src

The string to append to it

size_tcount

The size of the destination buffer.

intstrcmp(const char * cs, const char * ct)¶

Compare two strings

Parameters

constchar*cs

One string

constchar*ct

Another string

intstrncmp(const char * cs, const char * ct, size_t count)¶

Compare two length-limited strings

Parameters

constchar*cs

One string

constchar*ct

Another string

size_tcount

The maximum number of bytes to compare

char *strchr(const char * s, int c)¶

Find the first occurrence of a character in a string

Parameters

constchar*s

The string to be searched

intc

The character to search for

Description

Note that theNUL-terminator is considered part of the string, and canbe searched for.

char *strchrnul(const char * s, int c)¶

Find and return a character in a string, or end of string

Parameters

constchar*s

The string to be searched

intc

The character to search for

Description

Returns pointer to first occurrence of ‘c’ in s. If c is not found, thenreturn a pointer to the null byte at the end of s.

char *strrchr(const char * s, int c)¶

Find the last occurrence of a character in a string

Parameters

constchar*s

The string to be searched

intc

The character to search for

char *strnchr(const char * s, size_t count, int c)¶

Find a character in a length limited string

Parameters

constchar*s

The string to be searched

size_tcount

The number of characters to be searched

intc

The character to search for

Description

Note that theNUL-terminator is considered part of the string, and canbe searched for.

char *skip_spaces(const char * str)¶

Removes leading whitespace fromstr.

Parameters

constchar*str

The string to be stripped.

Description

Returns a pointer to the first non-whitespace character instr.

char *strim(char * s)¶

Removes leading and trailing whitespace froms.

Parameters

char*s

The string to be stripped.

Description

Note that the first trailing whitespace is replaced with aNUL-terminatorin the given strings. Returns a pointer to the first non-whitespacecharacter ins.

size_tstrlen(const char * s)¶

Find the length of a string

Parameters

constchar*s

The string to be sized

size_tstrnlen(const char * s, size_t count)¶

Find the length of a length-limited string

Parameters

constchar*s

The string to be sized

size_tcount

The maximum number of bytes to search

size_tstrspn(const char * s, const char * accept)¶

Calculate the length of the initial substring ofs which only contain letters inaccept

Parameters

constchar*s

The string to be searched

constchar*accept

The string to search for

size_tstrcspn(const char * s, const char * reject)¶

Calculate the length of the initial substring ofs which does not contain letters inreject

Parameters

constchar*s

The string to be searched

constchar*reject

The string to avoid

char *strpbrk(const char * cs, const char * ct)¶

Find the first occurrence of a set of characters

Parameters

constchar*cs

The string to be searched

constchar*ct

The characters to search for

char *strsep(char ** s, const char * ct)¶

Split a string into tokens

Parameters

char**s

The string to be searched

constchar*ct

The characters to search for

Description

strsep() updatess to point after the token, ready for the next call.

It returns empty tokens, too, behaving exactly like the libc functionof that name. In fact, it was stolen from glibc2 and de-fancy-fied.Same semantics, slimmer shape. ;)

boolsysfs_streq(const char * s1, const char * s2)¶

return true if strings are equal, modulo trailing newline

Parameters

constchar*s1

one string

constchar*s2

another string

Description

This routine returns true iff two strings are equal, treating bothNUL and newline-then-NUL as equivalent string terminations. It’sgeared for use with sysfs input strings, which generally terminatewith newlines but are compared against values without newlines.

intmatch_string(const char *const * array, size_t n, const char * string)¶

matches given string in an array

Parameters

constchar*const*array

array of strings

size_tn

number of strings in the array or -1 for NULL terminated arrays

constchar*string

string to match with

Description

This routine will look for a string in an array of strings up to then-th element in the array or until the first NULL element.

Historically the value of -1 forn, was used to search in arrays thatare NULL terminated. However, the function does not make a distinctionwhen finishing the search: eithern elements have been compared ORthe first NULL element was found.

Return

index of astring in thearray if matches, or-EINVAL otherwise.

int__sysfs_match_string(const char *const * array, size_t n, const char * str)¶

matches given string in an array

Parameters

constchar*const*array

array of strings

size_tn

number of strings in the array or -1 for NULL terminated arrays

constchar*str

string to match with

Description

Returns index ofstr in thearray or -EINVAL, just likematch_string().Uses sysfs_streq instead of strcmp for matching.

This routine will look for a string in an array of strings up to then-th element in the array or until the first NULL element.

Historically the value of -1 forn, was used to search in arrays thatare NULL terminated. However, the function does not make a distinctionwhen finishing the search: eithern elements have been compared ORthe first NULL element was found.

void *memset(void * s, int c, size_t count)¶

Fill a region of memory with the given value

Parameters

void*s

Pointer to the start of the area.

intc

The byte to fill the area with

size_tcount

The size of the area.

Description

Do not usememset() to access IO space, use memset_io() instead.

void *memset16(uint16_t * s, uint16_t v, size_t count)¶

Fill a memory area with a uint16_t

Parameters

uint16_t*s

Pointer to the start of the area.

uint16_tv

The value to fill the area with

size_tcount

The number of values to store

Description

Differs frommemset() in that it fills with a uint16_t insteadof a byte. Remember thatcount is the number of uint16_ts tostore, not the number of bytes.

void *memset32(uint32_t * s, uint32_t v, size_t count)¶

Fill a memory area with a uint32_t

Parameters

uint32_t*s

Pointer to the start of the area.

uint32_tv

The value to fill the area with

size_tcount

The number of values to store

Description

Differs frommemset() in that it fills with a uint32_t insteadof a byte. Remember thatcount is the number of uint32_ts tostore, not the number of bytes.

void *memset64(uint64_t * s, uint64_t v, size_t count)¶

Fill a memory area with a uint64_t

Parameters

uint64_t*s

Pointer to the start of the area.

uint64_tv

The value to fill the area with

size_tcount

The number of values to store

Description

Differs frommemset() in that it fills with a uint64_t insteadof a byte. Remember thatcount is the number of uint64_ts tostore, not the number of bytes.

void *memcpy(void * dest, const void * src, size_t count)¶

Copy one area of memory to another

Parameters

void*dest

Where to copy to

constvoid*src

Where to copy from

size_tcount

The size of the area.

Description

You should not use this function to access IO space, use memcpy_toio()or memcpy_fromio() instead.

void *memmove(void * dest, const void * src, size_t count)¶

Copy one area of memory to another

Parameters

void*dest

Where to copy to

constvoid*src

Where to copy from

size_tcount

The size of the area.

Description

Unlikememcpy(),memmove() copes with overlapping areas.

__visible intmemcmp(const void * cs, const void * ct, size_t count)¶

Compare two areas of memory

Parameters

constvoid*cs

One area of memory

constvoid*ct

Another area of memory

size_tcount

The size of the area.

intbcmp(const void * a, const void * b, size_t len)¶

returns 0 if and only if the buffers have identical contents.

Parameters

constvoid*a

pointer to first buffer.

constvoid*b

pointer to second buffer.

size_tlen

size of buffers.

Description

The sign or magnitude of a non-zero return value has no particularmeaning, and architectures may implement their own more efficientbcmp(). Sowhile this particular implementation is a simple (tail) call to memcmp, donot rely on anything but whether the return value is zero or non-zero.

void *memscan(void * addr, int c, size_t size)¶

Find a character in an area of memory.

Parameters

void*addr

The memory area

intc

The byte to search for

size_tsize

The size of the area.

Description

returns the address of the first occurrence ofc, or 1 byte pastthe area ifc is not found

char *strstr(const char * s1, const char * s2)¶

Find the first substring in aNUL terminated string

Parameters

constchar*s1

The string to be searched

constchar*s2

The string to search for

char *strnstr(const char * s1, const char * s2, size_t len)¶

Find the first substring in a length-limited string

Parameters

constchar*s1

The string to be searched

constchar*s2

The string to search for

size_tlen

the maximum number of characters to search

void *memchr(const void * s, int c, size_t n)¶

Find a character in an area of memory.

Parameters

constvoid*s

The memory area

intc

The byte to search for

size_tn

The size of the area.

Description

returns the address of the first occurrence ofc, orNULLifc is not found

void *memchr_inv(const void * start, int c, size_t bytes)¶

Find an unmatching character in an area of memory.

Parameters

constvoid*start

The memory area

intc

Find a character other than c

size_tbytes

The size of the area.

Description

returns the address of the first character other thanc, orNULLif the whole buffer contains justc.

char *strreplace(char * s, char old, char new)¶

Replace all occurrences of character in string.

Parameters

char*s

The string to operate on.

charold

The character being replaced.

charnew

The characterold is replaced with.

Description

Returns pointer to the nul byte at the end ofs.

sysfs_match_string(_a,_s)¶

matches given string in an array

Parameters

_a

array of strings

_s

string to match with

Description

Helper for__sysfs_match_string(). Calculates the size ofa automatically.

boolstrstarts(const char * str, const char * prefix)¶

doesstr start withprefix?

Parameters

constchar*str

string to examine

constchar*prefix

prefix to look for.

voidmemzero_explicit(void * s, size_t count)¶

Fill a region of memory (e.g. sensitive keying data) with 0s.

Parameters

void*s

Pointer to the start of the area.

size_tcount

The size of the area.

Note

usually usingmemset() is just fine (!), but in caseswhere clearing out _local_ data at the end of a scope isnecessary,memzero_explicit() should be used instead inorder to prevent the compiler from optimising away zeroing.

Description

memzero_explicit() doesn’t need an arch-specific version asit just invokes the one ofmemset() implicitly.

const char *kbasename(const char * path)¶

return the last part of a pathname.

Parameters

constchar*path

path to extract the filename from.

voidmemcpy_and_pad(void * dest, size_t dest_len, const void * src, size_t count, int pad)¶

Copy one buffer to another with padding

Parameters

void*dest

Where to copy to

size_tdest_len

The destination buffer size

constvoid*src

Where to copy from

size_tcount

The number of bytes to copy

intpad

Character to use for padding if space is left in destination.

size_tstr_has_prefix(const char * str, const char * prefix)¶

Test if a string has a given prefix

Parameters

constchar*str

The string to test

constchar*prefix

The string to see ifstr starts with

Description

A common way to test a prefix of a string is to do:

strncmp(str, prefix, sizeof(prefix) - 1)

But this can lead to bugs due to typos, or if prefix is a pointerand not a constant. Instead usestr_has_prefix().

Return

• strlen(prefix) ifstr starts withprefix
• 0 ifstr does not start withprefix

char *kstrdup(const char * s, gfp_t gfp)¶

allocate space for and copy an existing string

Parameters

constchar*s

the string to duplicate

gfp_tgfp

the GFP mask used in thekmalloc() call when allocating memory

Return

newly allocated copy ofs orNULL in case of error

const char *kstrdup_const(const char * s, gfp_t gfp)¶

conditionally duplicate an existing const string

Parameters

constchar*s

the string to duplicate

gfp_tgfp

the GFP mask used in thekmalloc() call when allocating memory

Note

Strings allocated by kstrdup_const should be freed by kfree_const.

Return

source string if it is in .rodata section otherwisefallback to kstrdup.

char *kstrndup(const char * s, size_t max, gfp_t gfp)¶

allocate space for and copy an existing string

Parameters

constchar*s

the string to duplicate

size_tmax

read at mostmax chars froms

gfp_tgfp

the GFP mask used in thekmalloc() call when allocating memory

Note

Usekmemdup_nul() instead if the size is known exactly.

Return

newly allocated copy ofs orNULL in case of error

void *kmemdup(const void * src, size_t len, gfp_t gfp)¶

duplicate region of memory

Parameters

constvoid*src

memory region to duplicate

size_tlen

memory region length

gfp_tgfp

GFP mask to use

Return

newly allocated copy ofsrc orNULL in case of error

char *kmemdup_nul(const char * s, size_t len, gfp_t gfp)¶

Create a NUL-terminated string from unterminated data

Parameters

constchar*s

The data to stringify

size_tlen

The size of the data

gfp_tgfp

the GFP mask used in thekmalloc() call when allocating memory

Return

newly allocated copy ofs with NUL-termination orNULL incase of error

void *memdup_user(const void __user * src, size_t len)¶

duplicate memory region from user space

Parameters

constvoid__user*src

source address in user space

size_tlen

number of bytes to copy

Return

an ERR_PTR() on failure. Result is physicallycontiguous, to be freed bykfree().

void *vmemdup_user(const void __user * src, size_t len)¶

duplicate memory region from user space

Parameters

constvoid__user*src

source address in user space

size_tlen

number of bytes to copy

Return

an ERR_PTR() on failure. Result may be notphysically contiguous. Usekvfree() to free.

char *strndup_user(const char __user * s, long n)¶

duplicate an existing string from user space

Parameters

constchar__user*s

The string to duplicate

longn

Maximum number of bytes to copy, including the trailing NUL.

Return

newly allocated copy ofs or an ERR_PTR() in case of error

void *memdup_user_nul(const void __user * src, size_t len)¶

duplicate memory region from user space and NUL-terminate

Parameters

constvoid__user*src

source address in user space

size_tlen

number of bytes to copy

Return

an ERR_PTR() on failure.

Bit Operations¶

voidset_bit(long nr, volatile unsigned long * addr)¶

Atomically set a bit in memory

Parameters

longnr

the bit to set

volatileunsignedlong*addr

the address to start counting from

Description

This is a relaxed atomic operation (no implied memory barriers).

Note thatnr may be almost arbitrarily large; this function is notrestricted to acting on a single-word quantity.

voidclear_bit(long nr, volatile unsigned long * addr)¶

Clears a bit in memory

Parameters

longnr

Bit to clear

volatileunsignedlong*addr

Address to start counting from

Description

This is a relaxed atomic operation (no implied memory barriers).

voidchange_bit(long nr, volatile unsigned long * addr)¶

Toggle a bit in memory

Parameters

longnr

Bit to change

volatileunsignedlong*addr

Address to start counting from

Description

This is a relaxed atomic operation (no implied memory barriers).

Note thatnr may be almost arbitrarily large; this function is notrestricted to acting on a single-word quantity.

booltest_and_set_bit(long nr, volatile unsigned long * addr)¶

Set a bit and return its old value

Parameters

longnr

Bit to set

volatileunsignedlong*addr

Address to count from

Description

This is an atomic fully-ordered operation (implied full memory barrier).

booltest_and_clear_bit(long nr, volatile unsigned long * addr)¶

Clear a bit and return its old value

Parameters

longnr

Bit to clear

volatileunsignedlong*addr

Address to count from

Description

This is an atomic fully-ordered operation (implied full memory barrier).

booltest_and_change_bit(long nr, volatile unsigned long * addr)¶

Change a bit and return its old value

Parameters

longnr

Bit to change

volatileunsignedlong*addr

Address to count from

Description

This is an atomic fully-ordered operation (implied full memory barrier).

void__set_bit(long nr, volatile unsigned long * addr)¶

Set a bit in memory

Parameters

longnr

the bit to set

volatileunsignedlong*addr

the address to start counting from

Description

Unlikeset_bit(), this function is non-atomic. If it is called on the sameregion of memory concurrently, the effect may be that only one operationsucceeds.

void__clear_bit(long nr, volatile unsigned long * addr)¶

Clears a bit in memory

Parameters

longnr

the bit to clear

volatileunsignedlong*addr

the address to start counting from

Description

Unlikeclear_bit(), this function is non-atomic. If it is called on the sameregion of memory concurrently, the effect may be that only one operationsucceeds.

void__change_bit(long nr, volatile unsigned long * addr)¶

Toggle a bit in memory

Parameters

longnr

the bit to change

volatileunsignedlong*addr

the address to start counting from

Description

Unlikechange_bit(), this function is non-atomic. If it is called on the sameregion of memory concurrently, the effect may be that only one operationsucceeds.

bool__test_and_set_bit(long nr, volatile unsigned long * addr)¶

Set a bit and return its old value

Parameters

longnr

Bit to set

volatileunsignedlong*addr

Address to count from

Description

This operation is non-atomic. If two instances of this operation race, onecan appear to succeed but actually fail.

bool__test_and_clear_bit(long nr, volatile unsigned long * addr)¶

Clear a bit and return its old value

Parameters

longnr

Bit to clear

volatileunsignedlong*addr

Address to count from

Description

This operation is non-atomic. If two instances of this operation race, onecan appear to succeed but actually fail.

bool__test_and_change_bit(long nr, volatile unsigned long * addr)¶

Change a bit and return its old value

Parameters

longnr

Bit to change

volatileunsignedlong*addr

Address to count from

Description

This operation is non-atomic. If two instances of this operation race, onecan appear to succeed but actually fail.

booltest_bit(long nr, const volatile unsigned long * addr)¶

Determine whether a bit is set

Parameters

longnr

bit number to test

constvolatileunsignedlong*addr

Address to start counting from

voidclear_bit_unlock(long nr, volatile unsigned long * addr)¶

Clear a bit in memory, for unlock

Parameters

longnr

the bit to set

volatileunsignedlong*addr

the address to start counting from

Description

This operation is atomic and provides release barrier semantics.

void__clear_bit_unlock(long nr, volatile unsigned long * addr)¶

Clears a bit in memory

Parameters

longnr

Bit to clear

volatileunsignedlong*addr

Address to start counting from

Description

This is a non-atomic operation but implies a release barrier before thememory operation. It can be used for an unlock if no other CPUs canconcurrently modify other bits in the word.

booltest_and_set_bit_lock(long nr, volatile unsigned long * addr)¶

Set a bit and return its old value, for lock

Parameters

longnr

Bit to set

volatileunsignedlong*addr

Address to count from

Description

This operation is atomic and provides acquire barrier semantics ifthe returned value is 0.It can be used to implement bit locks.

boolclear_bit_unlock_is_negative_byte(long nr, volatile unsigned long * addr)¶

Clear a bit in memory and test if bottom byte is negative, for unlock.

Parameters

longnr

the bit to clear

volatileunsignedlong*addr

the address to start counting from

Description

This operation is atomic and provides release barrier semantics.

This is a bit of a one-trick-pony for the filemap code, which clearsPG_locked and tests PG_waiters,

Bitmap Operations¶

bitmaps provide an array of bits, implemented using an anarray of unsigned longs. The number of valid bits in agiven bitmap does _not_ need to be an exact multiple ofBITS_PER_LONG.

The possible unused bits in the last, partially used wordof a bitmap are ‘don’t care’. The implementation makesno particular effort to keep them zero. It ensures thattheir value will not affect the results of any operation.The bitmap operations that return Boolean (bitmap_empty,for example) or scalar (bitmap_weight, for example) resultscarefully filter out these unused bits from impacting theirresults.

The byte ordering of bitmaps is more natural on littleendian architectures. See the big-endian headersinclude/asm-ppc64/bitops.h and include/asm-s390/bitops.hfor the best explanations of this ordering.

The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be usedto declare an array named ‘name’ of just enough unsigned longs tocontain all bit positions from 0 to ‘bits’ - 1.

The available bitmap operations and their rough meaning in thecase that the bitmap is a single unsigned long are thus:

The generated code is more efficient when nbits is known atcompile-time and at most BITS_PER_LONG.

bitmap_zero(dst, nbits)                     *dst = 0ULbitmap_fill(dst, nbits)                     *dst = ~0ULbitmap_copy(dst, src, nbits)                *dst = *srcbitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)bitmap_complement(dst, src, nbits)          *dst = ~(*src)bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?bitmap_empty(src, nbits)                    Are all bits zero in *src?bitmap_full(src, nbits)                     Are all bits set in *src?bitmap_weight(src, nbits)                   Hamming Weight: number set bitsbitmap_set(dst, pos, nbits)                 Set specified bit areabitmap_clear(dst, pos, nbits)               Clear specified bit areabitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free areabitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off)  as abovebitmap_next_clear_region(map, :c:type:`start`, :c:type:`end`, nbits)  Find next clear regionbitmap_next_set_region(map, :c:type:`start`, :c:type:`end`, nbits)  Find next set regionbitmap_for_each_clear_region(map, rs, re, start, end)                                            Iterate over all clear regionsbitmap_for_each_set_region(map, rs, re, start, end)                                            Iterate over all set regionsbitmap_shift_right(dst, src, n, nbits)      *dst = *src >> nbitmap_shift_left(dst, src, n, nbits)       *dst = *src << nbitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy restbitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmapbitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod szbitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel bufbitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user bufbitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel bufbitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user bufbitmap_find_free_region(bitmap, bits, order)  Find and allocate bit regionbitmap_release_region(bitmap, pos, order)   Free specified bit regionbitmap_allocate_region(bitmap, pos, order)  Allocate specified bit regionbitmap_from_arr32(dst, buf, nbits)          Copy nbits from u32[] buf to dstbitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dstbitmap_get_value8(map, start)               Get 8bit value from map at startbitmap_set_value8(map, value, start)        Set 8bit value to map at start

Note, bitmap_zero() and bitmap_fill() operate over the region ofunsigned longs, that is, bits behind bitmap till the unsigned longboundary will be zeroed or filled as well. Consider to usebitmap_clear() or bitmap_set() to make explicit zeroing or fillingrespectively.

Also the following operations in asm/bitops.h apply to bitmaps.:

set_bit(bit, addr)                  *addr |= bitclear_bit(bit, addr)                *addr &= ~bitchange_bit(bit, addr)               *addr ^= bittest_bit(bit, addr)                 Is bit set in *addr?test_and_set_bit(bit, addr)         Set bit and return old valuetest_and_clear_bit(bit, addr)       Clear bit and return old valuetest_and_change_bit(bit, addr)      Change bit and return old valuefind_first_zero_bit(addr, nbits)    Position first zero bit in *addrfind_first_bit(addr, nbits)         Position first set bit in *addrfind_next_zero_bit(addr, nbits, bit)                                    Position next zero bit in *addr >= bitfind_next_bit(addr, nbits, bit)     Position next set bit in *addr >= bitfind_next_and_bit(addr1, addr2, nbits, bit)                                    Same as find_next_bit, but in                                    (*addr1 & *addr2)

void__bitmap_shift_right(unsigned long * dst, const unsigned long * src, unsigned shift, unsigned nbits)¶

logical right shift of the bits in a bitmap

Parameters

unsignedlong*dst

destination bitmap

constunsignedlong*src

source bitmap

unsignedshift

shift by this many bits

unsignednbits

bitmap size, in bits

Description

Shifting right (dividing) means moving bits in the MS -> LS bitdirection. Zeros are fed into the vacated MS positions and theLS bits shifted off the bottom are lost.

void__bitmap_shift_left(unsigned long * dst, const unsigned long * src, unsigned int shift, unsigned int nbits)¶

logical left shift of the bits in a bitmap

Parameters

unsignedlong*dst

destination bitmap

constunsignedlong*src

source bitmap

unsignedintshift

shift by this many bits

unsignedintnbits

bitmap size, in bits

Description

Shifting left (multiplying) means moving bits in the LS -> MSdirection. Zeros are fed into the vacated LS bit positionsand those MS bits shifted off the top are lost.

voidbitmap_cut(unsigned long * dst, const unsigned long * src, unsigned int first, unsigned int cut, unsigned int nbits)¶

remove bit region from bitmap and right shift remaining bits

Parameters

unsignedlong*dst

destination bitmap, might overlap with src

constunsignedlong*src

source bitmap

unsignedintfirst

start bit of region to be removed

unsignedintcut

number of bits to remove

unsignedintnbits

bitmap size, in bits

Description

Set the n-th bit ofdst iff the n-th bit ofsrc is set andn is less thanfirst, or the m-th bit ofsrc is set for anym such thatfirst <= n < nbits, and m = n +cut.

In pictures, example for a big-endian 32-bit architecture:

Thesrc bitmap is:

31                                   63|                                    |10000000 11000001 11110010 00010101  10000000 11000001 01110010 00010101                |  |              |                                    |               16  14             0                                   32

ifcut is 3, andfirst is 14, bits 14-16 insrc are cut anddst is:

31                                   63|                                    |10110000 00011000 00110010 00010101  00010000 00011000 00101110 01000010                   |              |                                    |                   14 (bit 17     0                                   32                       from @src)

Note thatdst andsrc might overlap partially or entirely.

This is implemented in the obvious way, with a shift and carrystep for each moved bit. Optimisation is left as an exercisefor the compiler.

unsigned longbitmap_find_next_zero_area_off(unsigned long * map, unsigned long size, unsigned long start, unsigned int nr, unsigned long align_mask, unsigned long align_offset)¶

find a contiguous aligned zero area

Parameters

unsignedlong*map

The address to base the search on

unsignedlongsize

The bitmap size in bits

unsignedlongstart

The bitnumber to start searching at

unsignedintnr

The number of zeroed bits we’re looking for

unsignedlongalign_mask

Alignment mask for zero area

unsignedlongalign_offset

Alignment offset for zero area.

Description

Thealign_mask should be one less than a power of 2; the effect is thatthe bit offset of all zero areas this function finds plusalign_offsetis multiple of that power of 2.

intbitmap_parse_user(const char __user * ubuf, unsigned int ulen, unsigned long * maskp, int nmaskbits)¶

convert an ASCII hex string in a user buffer into a bitmap

Parameters

constchar__user*ubuf

pointer to user buffer containing string.

unsignedintulen

buffer size in bytes. If string is smaller than thisthen it must be terminated with a 0.

unsignedlong*maskp

pointer to bitmap array that will contain result.

intnmaskbits

size of bitmap, in bits.

intbitmap_print_to_pagebuf(bool list, char * buf, const unsigned long * maskp, int nmaskbits)¶

convert bitmap to list or hex format ASCII string

Parameters

boollist

indicates whether the bitmap must be list

char*buf

page aligned buffer into which string is placed

constunsignedlong*maskp

pointer to bitmap to convert

intnmaskbits

size of bitmap, in bits

Description

Output format is a comma-separated list of decimal numbers andranges if list is specified or hex digits grouped into comma-separatedsets of 8 digits/set. Returns the number of characters written to buf.

It is assumed thatbuf is a pointer into a PAGE_SIZE, page-alignedarea and that sufficient storage remains atbuf to accommodate thebitmap_print_to_pagebuf() output. Returns the number of charactersactually printed tobuf, excluding terminating ‘0’.

intbitmap_parselist(const char * buf, unsigned long * maskp, int nmaskbits)¶

convert list format ASCII string to bitmap

Parameters

constchar*buf

read user string from this buffer; must be terminatedwith a 0 or n.

unsignedlong*maskp

write resulting mask here

intnmaskbits

number of bits in mask to be written

Description

Input format is a comma-separated list of decimal numbers andranges. Consecutively set bits are shown as two hyphen-separateddecimal numbers, the smallest and largest bit numbers set inthe range.Optionally each range can be postfixed to denote that only parts of itshould be set. The range will divided to groups of specific size.From each group will be used only defined amount of bits.Syntax: range:used_size/group_size

Example

0-1023:2/256 ==> 0,1,256,257,512,513,768,769

Return

0 on success, -errno on invalid input strings. Error values:

• -EINVAL: wrong region format
• -EINVAL: invalid character in string
• -ERANGE: bit number specified too large for mask
• -EOVERFLOW: integer overflow in the input parameters

intbitmap_parselist_user(const char __user * ubuf, unsigned int ulen, unsigned long * maskp, int nmaskbits)¶

Parameters

constchar__user*ubuf

pointer to user buffer containing string.

unsignedintulen

buffer size in bytes. If string is smaller than thisthen it must be terminated with a 0.

unsignedlong*maskp

pointer to bitmap array that will contain result.

intnmaskbits

size of bitmap, in bits.

Description

Wrapper forbitmap_parselist(), providing it with user buffer.

intbitmap_parse(const char * start, unsigned int buflen, unsigned long * maskp, int nmaskbits)¶

convert an ASCII hex string into a bitmap.

Parameters

constchar*start

pointer to buffer containing string.

unsignedintbuflen

buffer size in bytes. If string is smaller than thisthen it must be terminated with a 0 or n. In that case,UINT_MAX may be provided instead of string length.

unsignedlong*maskp

pointer to bitmap array that will contain result.

intnmaskbits

size of bitmap, in bits.

Description

Commas group hex digits into chunks. Each chunk defines exactly 32bits of the resultant bitmask. No chunk may specify a value largerthan 32 bits (-EOVERFLOW), and if a chunk specifies a smaller valuethen leading 0-bits are prepended.-EINVAL is returned for illegalcharacters. Grouping such as “1,,5”, “,44”, “,” or “” is allowed.Leading, embedded and trailing whitespace accepted.

intbitmap_find_free_region(unsigned long * bitmap, unsigned int bits, int order)¶

find a contiguous aligned mem region

Parameters

unsignedlong*bitmap

array of unsigned longs corresponding to the bitmap

unsignedintbits

number of bits in the bitmap

intorder

region size (log base 2 of number of bits) to find

Description

Find a region of free (zero) bits in abitmap ofbits bits andallocate them (set them to one). Only consider regions of lengtha power (order) of two, aligned to that power of two, whichmakes the search algorithm much faster.

Return the bit offset in bitmap of the allocated region,or -errno on failure.

voidbitmap_release_region(unsigned long * bitmap, unsigned int pos, int order)¶

release allocated bitmap region

Parameters

unsignedlong*bitmap

array of unsigned longs corresponding to the bitmap

unsignedintpos

beginning of bit region to release

intorder

region size (log base 2 of number of bits) to release

Description

This is the complement to __bitmap_find_free_region() and releasesthe found region (by clearing it in the bitmap).

No return value.

intbitmap_allocate_region(unsigned long * bitmap, unsigned int pos, int order)¶

allocate bitmap region

Parameters

unsignedlong*bitmap

array of unsigned longs corresponding to the bitmap

unsignedintpos

beginning of bit region to allocate

intorder

region size (log base 2 of number of bits) to allocate

Description

Allocate (set bits in) a specified region of a bitmap.

Return 0 on success, or-EBUSY if specified region wasn’tfree (not all bits were zero).

voidbitmap_copy_le(unsigned long * dst, const unsigned long * src, unsigned int nbits)¶

copy a bitmap, putting the bits into little-endian order.

Parameters

unsignedlong*dst

destination buffer

constunsignedlong*src

bitmap to copy

unsignedintnbits

number of bits in the bitmap

Description

Require nbits % BITS_PER_LONG == 0.

voidbitmap_from_arr32(unsigned long * bitmap, const u32 * buf, unsigned int nbits)¶

copy the contents of u32 array of bits to bitmap

Parameters

unsignedlong*bitmap

array of unsigned longs, the destination bitmap

constu32*buf

array of u32 (in host byte order), the source bitmap

unsignedintnbits

number of bits inbitmap

voidbitmap_to_arr32(u32 * buf, const unsigned long * bitmap, unsigned int nbits)¶

copy the contents of bitmap to a u32 array of bits

Parameters

u32*buf

array of u32 (in host byte order), the dest bitmap

constunsignedlong*bitmap

array of unsigned longs, the source bitmap

unsignedintnbits

number of bits inbitmap

intbitmap_pos_to_ord(const unsigned long * buf, unsigned int pos, unsigned int nbits)¶

find ordinal of set bit at given position in bitmap

Parameters

constunsignedlong*buf

pointer to a bitmap

unsignedintpos

a bit position inbuf (0 <=pos <nbits)

unsignedintnbits

number of valid bit positions inbuf

Description

Map the bit at positionpos inbuf (of lengthnbits) to theordinal of which set bit it is. If it is not set or ifposis not a valid bit position, map to -1.

If for example, just bits 4 through 7 are set inbuf, thenposvalues 4 through 7 will get mapped to 0 through 3, respectively,and otherpos values will get mapped to -1. Whenpos value 7gets mapped to (returns)ord value 3 in this example, that meansthat bit 7 is the 3rd (starting with 0th) set bit inbuf.

The bit positions 0 throughbits are valid positions inbuf.

unsigned intbitmap_ord_to_pos(const unsigned long * buf, unsigned int ord, unsigned int nbits)¶

find position of n-th set bit in bitmap

Parameters

constunsignedlong*buf

pointer to bitmap

unsignedintord

ordinal bit position (n-th set bit, n >= 0)

unsignedintnbits

number of valid bit positions inbuf

Description

Map the ordinal offset of bitord inbuf to its position inbuf.Value oford should be in range 0 <=ord < weight(buf). Iford>= weight(buf), returnsnbits.

If for example, just bits 4 through 7 are set inbuf, thenordvalues 0 through 3 will get mapped to 4 through 7, respectively,and all otherord values returnsnbits. Whenord value 3gets mapped to (returns)pos value 7 in this example, that meansthat the 3rd set bit (starting with 0th) is at position 7 inbuf.

The bit positions 0 throughnbits-1 are valid positions inbuf.

voidbitmap_remap(unsigned long * dst, const unsigned long * src, const unsigned long * old, const unsigned long * new, unsigned int nbits)¶

Apply map defined by a pair of bitmaps to another bitmap

Parameters

unsignedlong*dst

remapped result

constunsignedlong*src

subset to be remapped

constunsignedlong*old

defines domain of map

constunsignedlong*new

defines range of map

unsignedintnbits

number of bits in each of these bitmaps

Description

Letold andnew define a mapping of bit positions, such thatwhatever position is held by the n-th set bit inold is mappedto the n-th set bit innew. In the more general case, allowingfor the possibility that the weight ‘w’ ofnew is less than theweight ofold, map the position of the n-th set bit inold tothe position of the m-th set bit innew, where m == n % w.

If either of theold andnew bitmaps are empty, or ifsrc anddst point to the same location, then this routine copiessrctodst.

The positions of unset bits inold are mapped to themselves(the identify map).

Apply the above specified mapping tosrc, placing the result indst, clearing any bits previously set indst.

For example, lets say thatold has bits 4 through 7 set, andnew has bits 12 through 15 set. This defines the mapping of bitposition 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all otherbit positions unchanged. So if saysrc comes into this routinewith bits 1, 5 and 7 set, thendst should leave with bits 1,13 and 15 set.

intbitmap_bitremap(int oldbit, const unsigned long * old, const unsigned long * new, int bits)¶

Apply map defined by a pair of bitmaps to a single bit

Parameters

intoldbit

bit position to be mapped

constunsignedlong*old

defines domain of map

constunsignedlong*new

defines range of map

intbits

number of bits in each of these bitmaps

Description

Letold andnew define a mapping of bit positions, such thatwhatever position is held by the n-th set bit inold is mappedto the n-th set bit innew. In the more general case, allowingfor the possibility that the weight ‘w’ ofnew is less than theweight ofold, map the position of the n-th set bit inold tothe position of the m-th set bit innew, where m == n % w.

The positions of unset bits inold are mapped to themselves(the identify map).

Apply the above specified mapping to bit positionoldbit, returningthe new bit position.

For example, lets say thatold has bits 4 through 7 set, andnew has bits 12 through 15 set. This defines the mapping of bitposition 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all otherbit positions unchanged. So if sayoldbit is 5, then this routinereturns 13.

voidbitmap_onto(unsigned long * dst, const unsigned long * orig, const unsigned long * relmap, unsigned int bits)¶

translate one bitmap relative to another

Parameters

unsignedlong*dst

resulting translated bitmap

constunsignedlong*orig

original untranslated bitmap

constunsignedlong*relmap

bitmap relative to which translated

unsignedintbits

number of bits in each of these bitmaps

Description

Set the n-th bit ofdst iff there exists some m such that then-th bit ofrelmap is set, the m-th bit oforig is set, andthe n-th bit ofrelmap is also the m-th _set_ bit ofrelmap.(If you understood the previous sentence the first time yourread it, you’re overqualified for your current job.)

In other words,orig is mapped onto (surjectively)dst,using the map { <n, m> | the n-th bit ofrelmap is them-th set bit ofrelmap }.

Any set bits inorig above bit number W, where W is theweight of (number of set bits in)relmap are mapped nowhere.In particular, if for all bits m set inorig, m >= W, thendst will end up empty. In situations where the possibilityof such an empty result is not desired, one way to avoid it isto use thebitmap_fold() operator, below, to first fold theorig bitmap over itself so that all its set bits x are in therange 0 <= x < W. Thebitmap_fold() operator does this bysetting the bit (m % W) indst, for each bit (m) set inorig.

Example [1] for bitmap_onto():

Let’s sayrelmap has bits 30-39 set, andorig has bits1, 3, 5, 7, 9 and 11 set. Then on return from this routine,dst will have bits 31, 33, 35, 37 and 39 set.

When bit 0 is set inorig, it means turn on the bit indst corresponding to whatever is the first bit (if any)that is turned on inrelmap. Since bit 0 was off in theabove example, we leave off that bit (bit 30) indst.

When bit 1 is set inorig (as in the above example), itmeans turn on the bit indst corresponding to whateveris the second bit that is turned on inrelmap. The secondbit inrelmap that was turned on in the above example wasbit 31, so we turned on bit 31 indst.

Similarly, we turned on bits 33, 35, 37 and 39 indst,because they were the 4th, 6th, 8th and 10th set bitsset inrelmap, and the 4th, 6th, 8th and 10th bits oforig (i.e. bits 3, 5, 7 and 9) were also set.

When bit 11 is set inorig, it means turn on the bit indst corresponding to whatever is the twelfth bit that isturned on inrelmap. In the above example, there wereonly ten bits turned on inrelmap (30..39), so that bit11 was set inorig had no affect ondst.

Example [2] for bitmap_fold() + bitmap_onto():

Let’s sayrelmap has these ten bits set:

40 41 42 43 45 48 53 61 74 95

(for the curious, that’s 40 plus the first ten terms of theFibonacci sequence.)

Further lets say we use the following code, invokingbitmap_fold() then bitmap_onto, as suggested above toavoid the possibility of an emptydst result:

unsigned long *tmp;     // a temporary bitmap's bitsbitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);bitmap_onto(dst, tmp, relmap, bits);

Then this table shows what various values ofdst would be, forvariousorig’s. I list the zero-based positions of each set bit.The tmp column shows the intermediate result, as computed byusingbitmap_fold() to fold theorig bitmap modulo ten(the weight ofrelmap):

orig	tmp	dst
0	0	40
1	1	41
9	9	95
10	0	40[1]
1 3 5 7	1 3 5 7	41 43 48 61
0 1 2 3 4	0 1 2 3 4	40 41 42 43 45
0 9 18 27	0 9 8 7	40 61 74 95
0 10 20 30	0	40
0 11 22 33	0 1 2 3	40 41 42 43
0 12 24 36	0 2 4 6	40 42 45 53
78 102 211	1 2 8	41 42 74[1]

If either oforig orrelmap is empty (no set bits), thendstwill be returned empty.

If (as explained above) the only set bits inorig are in positionsm where m >= W, (where W is the weight ofrelmap) thendst willonce again be returned empty.

All bits indst not set by the above rule are cleared.

voidbitmap_fold(unsigned long * dst, const unsigned long * orig, unsigned int sz, unsigned int nbits)¶

fold larger bitmap into smaller, modulo specified size

Parameters

unsignedlong*dst

resulting smaller bitmap

constunsignedlong*orig

original larger bitmap

unsignedintsz

specified size

unsignedintnbits

number of bits in each of these bitmaps

Description

For each bit oldbit inorig, set bit oldbit modsz indst.Clear all other bits indst. See further the comment andExample [2] forbitmap_onto() for why and how to use this.

unsigned longbitmap_find_next_zero_area(unsigned long * map, unsigned long size, unsigned long start, unsigned int nr, unsigned long align_mask)¶

find a contiguous aligned zero area

Parameters

unsignedlong*map

The address to base the search on

unsignedlongsize

The bitmap size in bits

unsignedlongstart

The bitnumber to start searching at

unsignedintnr

The number of zeroed bits we’re looking for

unsignedlongalign_mask

Alignment mask for zero area

Description

Thealign_mask should be one less than a power of 2; the effect is thatthe bit offset of all zero areas this function finds is multiples of thatpower of 2. Aalign_mask of 0 means no alignment is required.

boolbitmap_or_equal(const unsigned long * src1, const unsigned long * src2, const unsigned long * src3, unsigned int nbits)¶

Check whether the or of two bitmaps is equal to a third

Parameters

constunsignedlong*src1

Pointer to bitmap 1

constunsignedlong*src2

Pointer to bitmap 2 will be or’ed with bitmap 1

constunsignedlong*src3

Pointer to bitmap 3. Compare to the result of*src1 |*src2

unsignedintnbits

number of bits in each of these bitmaps

Return

True if (*src1 |*src2) ==*src3, false otherwise

BITMAP_FROM_U64(n)¶

Represent u64 value in the format suitable for bitmap.

Parameters

n

u64 value

Description

Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bitintegers in 32-bit environment, and 64-bit integers in 64-bit one.

There are four combinations of endianness and length of the word in linuxABIs: LE64, BE64, LE32 and BE32.

On 64-bit kernels 64-bit LE and BE numbers are naturally ordered inbitmaps and therefore don’t require any special handling.

On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memoryprior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on theother hand is represented as an array of 32-bit words and the position ofbit N may therefore be calculated as: word #(N/32) and bit #(N``32``) in thatword. For example, bit #42 is located at 10th position of 2nd word.It matches 32-bit LE ABI, and we can simply let the compiler store 64-bitvalues in memory as it usually does. But for BE we need to swap hi and lowords manually.

With all that, the macroBITMAP_FROM_U64() does explicit reordering of hi andlo parts of u64. For LE32 it does nothing, and for BE environment it swapshi and lo words, as is expected by bitmap.

voidbitmap_from_u64(unsigned long * dst, u64 mask)¶

Check and swap words within u64.

Parameters

unsignedlong*dst

destination bitmap

u64mask

source bitmap

Description

In 32-bit Big Endian kernel, when using(u32*)(:c:type:`val`)[*]to read u64 mask, we will get the wrong word.That is(u32*)(:c:type:`val`)[0] gets the upper 32 bits,but we expect the lower 32-bits of u64.

unsigned longbitmap_get_value8(const unsigned long * map, unsigned long start)¶

get an 8-bit value within a memory region

Parameters

constunsignedlong*map

address to the bitmap memory region

unsignedlongstart

bit offset of the 8-bit value; must be a multiple of 8

Description

Returns the 8-bit value located at thestart bit offset within thesrcmemory region.

voidbitmap_set_value8(unsigned long * map, unsigned long value, unsigned long start)¶

set an 8-bit value within a memory region

Parameters

unsignedlong*map

address to the bitmap memory region

unsignedlongvalue

the 8-bit value; values wider than 8 bits may clobber bitmap

unsignedlongstart

bit offset of the 8-bit value; must be a multiple of 8

Command-line Parsing¶

intget_option(char ** str, int * pint)¶

Parse integer from an option string

Parameters

char**str

option string

int*pint

(output) integer value parsed fromstr

Read an int from an option string; if available accept a subsequentcomma as well.

Return values:0 - no int in string1 - int found, no subsequent comma2 - int found including a subsequent comma3 - hyphen found to denote a range

char *get_options(const char * str, int nints, int * ints)¶

Parse a string into a list of integers

Parameters

constchar*str

String to be parsed

intnints

size of integer array

int*ints

integer array

This function parses a string containing a comma-separatedlist of integers, a hyphen-separated range of _positive_ integers,or a combination of both. The parse halts when the array isfull, or when no more numbers can be retrieved from thestring.

Return value is the character in the string which causedthe parse to end (typically a null terminator, ifstr iscompletely parseable).

unsigned long longmemparse(const char * ptr, char ** retptr)¶

parse a string with mem suffixes into a number

Parameters

constchar*ptr

Where parse begins

char**retptr

(output) Optional pointer to next char after parse completes

Parses a string into a number. The number stored atptr ispotentially suffixed with K, M, G, T, P, E.

Sorting¶

voidsort_r(void * base, size_t num, size_t size, cmp_r_func_t cmp_func, swap_func_t swap_func, const void * priv)¶

sort an array of elements

Parameters

void*base

pointer to data to sort

size_tnum

number of elements

size_tsize

size of each element

cmp_r_func_tcmp_func

pointer to comparison function

swap_func_tswap_func

pointer to swap function or NULL

constvoid*priv

third argument passed to comparison function

Description

This function does a heapsort on the given array. You may providea swap_func function if you need to do something more than a memorycopy (e.g. fix up pointers or auxiliary data), but the built-in swapavoids a slow retpoline and so is significantly faster.

Sorting time is O(n log n) both on average and worst-case. Whilequicksort is slightly faster on average, it suffers from exploitableO(n*n) worst-case behavior and extra memory requirements that makeit less suitable for kernel use.

voidlist_sort(void * priv, struct list_head * head, int (*cmp)(void *priv, struct list_head *a, struct list_head *b))¶

sort a list

Parameters

void*priv

private data, opaque tolist_sort(), passed tocmp

structlist_head*head

the list to sort

int(*)(void*priv,structlist_head*a,structlist_head*b)cmp

the elements comparison function

Description

The comparison funtioncmp must return > 0 ifa should sort afterb (“a >b” if you want an ascending sort), and <= 0 ifa shouldsort beforebor their original order should be preserved. It isalways called with the element that came first in the input ina,and list_sort is a stable sort, so it is not necessary to distinguishthea <b anda ==b cases.

This is compatible with two styles ofcmp function:- The traditional style which returns <0 / =0 / >0, or- Returning a boolean 0/1.The latter offers a chance to save a few cycles in the comparison(which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).

A good way to write a multi-word comparison is:

if (a->high != b->high)        return a->high > b->high;if (a->middle != b->middle)        return a->middle > b->middle;return a->low > b->low;

This mergesort is as eager as possible while always performing at least2:1 balanced merges. Given two pending sublists of size 2^k, they aremerged to a size-2^(k+1) list as soon as we have 2^k following elements.

Thus, it will avoid cache thrashing as long as 3*2^k elements canfit into the cache. Not quite as good as a fully-eager bottom-upmergesort, but it does use 0.2*n fewer comparisons, so is faster inthe common case that everything fits into L1.

The merging is controlled by “count”, the number of elements in thepending lists. This is beautiully simple code, but rather subtle.

Each time we increment “count”, we set one bit (bit k) and clearbits k-1 .. 0. Each time this happens (except the very first timefor each bit, when count increments to 2^k), we merge two lists ofsize 2^k into one list of size 2^(k+1).

This merge happens exactly when the count reaches an odd multiple of2^k, which is when we have 2^k elements pending in smaller lists,so it’s safe to merge away two lists of size 2^k.

After this happens twice, we have created two lists of size 2^(k+1),which will be merged into a list of size 2^(k+2) before we createa third list of size 2^(k+1), so there are never more than two pending.

The number of pending lists of size 2^k is determined by thestate of bit k of “count” plus two extra pieces of information:

• The state of bit k-1 (when k == 0, consider bit -1 always set), and
• Whether the higher-order bits are zero or non-zero (i.e.is count >= 2^(k+1)).

There are six states we distinguish. “x” represents some arbitrarybits, and “y” represents some arbitrary non-zero bits:0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k(merge and loop back to state 2)

We gain lists of size 2^k in the 2->3 and 4->5 transitions (becausebit k-1 is set while the more significant bits are non-zero) andmerge them away in the 5->2 transition. Note in particular that justbefore the 5->2 transition, all lower-order bits are 11 (state 3),so there is one list of each smaller size.

When we reach the end of the input, we merge all the pendinglists, from smallest to largest. If you work through cases 2 to5 above, you can see that the number of elements we merge with a listof size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).

Text Searching¶

INTRODUCTION

The textsearch infrastructure provides text searching facilities forboth linear and non-linear data. Individual search algorithms areimplemented in modules and chosen by the user.

ARCHITECTURE

  User  +----------------+  |        finish()|<--------------(6)-----------------+  |get_next_block()|<--------------(5)---------------+ |  |                |                     Algorithm   | |  |                |                    +------------------------------+  |                |                    |  init()   find()   destroy() |  |                |                    +------------------------------+  |                |       Core API           ^       ^          ^  |                |      +---------------+  (2)     (4)        (8)  |             (1)|----->| prepare()     |---+       |          |  |             (3)|----->| find()/next() |-----------+          |  |             (7)|----->| destroy()     |----------------------+  +----------------+      +---------------+(1) User configures a search by calling textsearch_prepare() specifying    the search parameters such as the pattern and algorithm name.(2) Core requests the algorithm to allocate and initialize a search    configuration according to the specified parameters.(3) User starts the search(es) by calling textsearch_find() or    textsearch_next() to fetch subsequent occurrences. A state variable    is provided to the algorithm to store persistent variables.(4) Core eventually resets the search offset and forwards the find()    request to the algorithm.(5) Algorithm calls get_next_block() provided by the user continuously    to fetch the data to be searched in block by block.(6) Algorithm invokes finish() after the last call to get_next_block    to clean up any leftovers from get_next_block. (Optional)(7) User destroys the configuration by calling textsearch_destroy().(8) Core notifies the algorithm to destroy algorithm specific    allocations. (Optional)

USAGE

Before a search can be performed, a configuration must be createdby callingtextsearch_prepare() specifying the searching algorithm,the pattern to look for and flags. As a flag, you can set TS_IGNORECASEto perform case insensitive matching. But it might slow downperformance of algorithm, so you should use it at own your risk.The returned configuration may then be used for an arbitraryamount of times and even in parallel as long as a separate structts_state variable is provided to every instance.

The actual search is performed by either callingtextsearch_find_continuous() for linear data or by providingan own get_next_block() implementation andcallingtextsearch_find(). Both functions returnthe position of the first occurrence of the pattern or UINT_MAX ifno match was found. Subsequent occurrences can be found by callingtextsearch_next() regardless of the linearity of the data.

Once you’re done using a configuration it must be given back viatextsearch_destroy.

EXAMPLE:

int pos;struct ts_config *conf;struct ts_state state;const char *pattern = "chicken";const char *example = "We dance the funky chicken";conf = textsearch_prepare("kmp", pattern, strlen(pattern),                          GFP_KERNEL, TS_AUTOLOAD);if (IS_ERR(conf)) {    err = PTR_ERR(conf);    goto errout;}pos = textsearch_find_continuous(conf, &state, example, strlen(example));if (pos != UINT_MAX)    panic("Oh my god, dancing chickens at %d\n", pos);textsearch_destroy(conf);

inttextsearch_register(struct ts_ops * ops)¶

register a textsearch module

Parameters

structts_ops*ops

operations lookup table

Description

This function must be called by textsearch modules to announcetheir presence. The specified &**ops** must havename set to aunique identifier and the callbacks find(), init(), get_pattern(),and get_pattern_len() must be implemented.

Returns 0 or -EEXISTS if another module has already registeredwith same name.

inttextsearch_unregister(struct ts_ops * ops)¶

unregister a textsearch module

Parameters

structts_ops*ops

operations lookup table

Description

This function must be called by textsearch modules to announcetheir disappearance for examples when the module gets unloaded.Theops parameter must be the same as the one during theregistration.

Returns 0 on success or -ENOENT if no matching textsearchregistration was found.

unsigned inttextsearch_find_continuous(struct ts_config * conf, struct ts_state * state, const void * data, unsigned int len)¶

search a pattern in continuous/linear data

Parameters

structts_config*conf

search configuration

structts_state*state

search state

constvoid*data

data to search in

unsignedintlen

length of data

Description

A simplified version oftextsearch_find() for continuous/linear data.Calltextsearch_next() to retrieve subsequent matches.

Returns the position of first occurrence of the pattern orUINT_MAX if no occurrence was found.

struct ts_config *textsearch_prepare(const char * algo, const void * pattern, unsigned int len, gfp_t gfp_mask, int flags)¶

Prepare a search

Parameters

constchar*algo

name of search algorithm

constvoid*pattern

pattern data

unsignedintlen

length of pattern

gfp_tgfp_mask

allocation mask

intflags

search flags

Description

Looks up the search algorithm module and creates a new textsearchconfiguration for the specified pattern.

Returns a new textsearch configuration according to the specifiedparameters or a ERR_PTR(). If a zero length pattern is passed, thisfunction returns EINVAL.

Note

The format of the pattern may not be compatible between

the various search algorithms.

voidtextsearch_destroy(struct ts_config * conf)¶

destroy a search configuration

Parameters

structts_config*conf

search configuration

Description

Releases all references of the configuration and freesup the memory.

unsigned inttextsearch_next(struct ts_config * conf, struct ts_state * state)¶

continue searching for a pattern

Parameters

structts_config*conf

search configuration

structts_state*state

search state

Description

Continues a search looking for more occurrences of the pattern.textsearch_find() must be called to find the first occurrencein order to reset the state.

Returns the position of the next occurrence of the pattern orUINT_MAX if not match was found.

unsigned inttextsearch_find(struct ts_config * conf, struct ts_state * state)¶

start searching for a pattern

Parameters

structts_config*conf

search configuration

structts_state*state

search state

Description

Returns the position of first occurrence of the pattern orUINT_MAX if no match was found.

void *textsearch_get_pattern(struct ts_config * conf)¶

return head of the pattern

Parameters

structts_config*conf

search configuration

unsigned inttextsearch_get_pattern_len(struct ts_config * conf)¶

return length of the pattern

Parameters

structts_config*conf

search configuration

CRC Functions¶

uint8_tcrc4(uint8_t c, uint64_t x, int bits)¶

calculate the 4-bit crc of a value.

Parameters

uint8_tc

starting crc4

uint64_tx

value to checksum

intbits

number of bits inx to checksum

Description

Returns the crc4 value ofx, using polynomial 0b10111.

Thex value is treated as left-aligned, and bits abovebits are ignoredin the crc calculations.

u8crc7_be(u8 crc, const u8 * buffer, size_t len)¶

update the CRC7 for the data buffer

Parameters

u8crc

previous CRC7 value

constu8*buffer

data pointer

size_tlen

number of bytes in the buffer

Context

any

Description

Returns the updated CRC7 value.The CRC7 is left-aligned in the byte (the lsbit is always 0), as thatmakes the computation easier, and all callers want it in that form.

voidcrc8_populate_msb(u8 table, u8 polynomial)¶

fill crc table for given polynomial in reverse bit order.

Parameters

u8table

table to be filled.

u8polynomial

polynomial for which table is to be filled.

voidcrc8_populate_lsb(u8 table, u8 polynomial)¶

fill crc table for given polynomial in regular bit order.

Parameters

u8table

table to be filled.

u8polynomial

polynomial for which table is to be filled.

u8crc8(const u8 table, u8 * pdata, size_t nbytes, u8 crc)¶

calculate a crc8 over the given input data.

Parameters

constu8table

crc table used for calculation.

u8*pdata

pointer to data buffer.

size_tnbytes

number of bytes in data buffer.

u8crc

previous returned crc8 value.

u16crc16(u16 crc, u8 const * buffer, size_t len)¶

compute the CRC-16 for the data buffer

Parameters

u16crc

previous CRC value

u8const*buffer

data pointer

size_tlen

number of bytes in the buffer

Description

Returns the updated CRC value.

u32 __purecrc32_le_generic(u32 crc, unsigned char const * p, size_t len, const u32 ( * tab, u32 polynomial)¶

Calculate bitwise little-endian Ethernet AUTODIN II CRC32/CRC32C

Parameters

u32crc

seed value for computation. ~0 for Ethernet, sometimes 0 for otheruses, or the previous crc32/crc32c value if computing incrementally.

unsignedcharconst*p

pointer to buffer over which CRC32/CRC32C is run

size_tlen

length of bufferp

constu32(*tab

little-endian Ethernet table

u32polynomial

CRC32/CRC32c LE polynomial

u32 __attribute_const__crc32_generic_shift(u32 crc, size_t len, u32 polynomial)¶

Appendlen 0 bytes to crc, in logarithmic time

Parameters

u32crc

The original little-endian CRC (i.e. lsbit is x^31 coefficient)

size_tlen

The number of bytes.crc is multiplied by x^(8***len**)

u32polynomial

The modulus used to reduce the result to 32 bits.

Description

It’s possible to parallelize CRC computations by computing a CRCover separate ranges of a buffer, then summing them.This shifts the given CRC by 8*len bits (i.e. produces the same effectas appending len bytes of zero to the data), in time proportionalto log(len).

u32 __purecrc32_be_generic(u32 crc, unsigned char const * p, size_t len, const u32 ( * tab, u32 polynomial)¶

Calculate bitwise big-endian Ethernet AUTODIN II CRC32

Parameters

u32crc

seed value for computation. ~0 for Ethernet, sometimes 0 forother uses, or the previous crc32 value if computing incrementally.

unsignedcharconst*p

pointer to buffer over which CRC32 is run

size_tlen

length of bufferp

constu32(*tab

big-endian Ethernet table

u32polynomial

CRC32 BE polynomial

u16crc_ccitt(u16 crc, u8 const * buffer, size_t len)¶

recompute the CRC (CRC-CCITT variant) for the data buffer

Parameters

u16crc

previous CRC value

u8const*buffer

data pointer

size_tlen

number of bytes in the buffer

u16crc_ccitt_false(u16 crc, u8 const * buffer, size_t len)¶

recompute the CRC (CRC-CCITT-FALSE variant) for the data buffer

Parameters

u16crc

previous CRC value

u8const*buffer

data pointer

size_tlen

number of bytes in the buffer

u16crc_itu_t(u16 crc, const u8 * buffer, size_t len)¶

Compute the CRC-ITU-T for the data buffer

Parameters

u16crc

previous CRC value

constu8*buffer

data pointer

size_tlen

number of bytes in the buffer

Description

Returns the updated CRC value

Base 2 log and power Functions¶

boolis_power_of_2(unsigned long n)¶

check if a value is a power of two

Parameters

unsignedlongn

the value to check

Description

Determine whether some value is a power of two, where zero isnot considered a power of two.

Return

true ifn is a power of 2, otherwise false.

unsigned long__roundup_pow_of_two(unsigned long n)¶

round up to nearest power of two

Parameters

unsignedlongn

value to round up

unsigned long__rounddown_pow_of_two(unsigned long n)¶

round down to nearest power of two

Parameters

unsignedlongn

value to round down

const_ilog2(n)¶

log base 2 of 32-bit or a 64-bit constant unsigned value

Parameters

n

parameter

Description

Use this where sparse expects a true constant expression, e.g. for arrayindices.

ilog2(n)¶

log base 2 of 32-bit or a 64-bit unsigned value

Parameters

n

parameter

Description

constant-capable log of base 2 calculation- this can be used to initialise global variables from constant data, hencethe massive ternary operator construction

selects the appropriately-sized optimised version depending on sizeof(n)

roundup_pow_of_two(n)¶

round the given value up to nearest power of two

Parameters

n

parameter

Description

round the given value up to the nearest power of two- the result is undefined when n == 0- this can be used to initialise global variables from constant data

rounddown_pow_of_two(n)¶

round the given value down to nearest power of two

Parameters

n

parameter

Description

round the given value down to the nearest power of two- the result is undefined when n == 0- this can be used to initialise global variables from constant data

order_base_2(n)¶

calculate the (rounded up) base 2 order of the argument

Parameters

n

parameter

Description

The first few values calculated by this routine:

ob2(0) = 0ob2(1) = 0ob2(2) = 1ob2(3) = 2ob2(4) = 2ob2(5) = 3… and so on.

bits_per(n)¶

calculate the number of bits required for the argument

Parameters

n

parameter

Description

This is constant-capable and can be used for compile timeinitializations, e.g bitfields.

The first few values calculated by this routine:bf(0) = 1bf(1) = 1bf(2) = 2bf(3) = 2bf(4) = 3… and so on.

Integer power Functions¶

u64int_pow(u64 base, unsigned int exp)¶

computes the exponentiation of the given base and exponent

Parameters

u64base

base which will be raised to the given power

unsignedintexp

power to be raised to