diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/crc32.h | 5 | ||||
| -rw-r--r-- | include/dictionary.h | 52 | ||||
| -rw-r--r-- | include/libiniparser.h | 218 | ||||
| -rw-r--r-- | include/libubi.h | 21 | ||||
| -rw-r--r-- | include/list.h | 263 | ||||
| -rw-r--r-- | include/mtd/ubi-user.h | 4 | ||||
| -rw-r--r-- | include/mtd/ubifs-media.h | 869 | ||||
| -rw-r--r-- | include/rbtree.h | 203 |
8 files changed, 680 insertions, 955 deletions
diff --git a/include/crc32.h b/include/crc32.h index 9c1f742..f5271f3 100644 --- a/include/crc32.h +++ b/include/crc32.h @@ -10,4 +10,9 @@ /* Return a 32-bit CRC of the contents of the buffer */ extern uint32_t mtd_crc32(uint32_t val, const void *ss, int len); +static inline uint32_t crc32(uint32_t val, const void *ss, int len) +{ + return mtd_crc32(val, ss, len); +} + #endif /* __CRC32_H__ */ diff --git a/include/dictionary.h b/include/dictionary.h index c7d1790..f459cfe 100644 --- a/include/dictionary.h +++ b/include/dictionary.h @@ -3,8 +3,6 @@ /** @file dictionary.h @author N. Devillard - @date Sep 2007 - @version $Revision: 1.12 $ @brief Implements a dictionary for string variables. This module implements a simple dictionary object, i.e. a list @@ -13,33 +11,27 @@ */ /*--------------------------------------------------------------------------*/ -/* - $Id: dictionary.h,v 1.12 2007-11-23 21:37:00 ndevilla Exp $ - $Author: ndevilla $ - $Date: 2007-11-23 21:37:00 $ - $Revision: 1.12 $ -*/ - #ifndef _DICTIONARY_H_ #define _DICTIONARY_H_ /*--------------------------------------------------------------------------- - Includes + Includes ---------------------------------------------------------------------------*/ #include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> + +#ifdef __cplusplus +extern "C" { +#endif /*--------------------------------------------------------------------------- - New types + New types ---------------------------------------------------------------------------*/ /*-------------------------------------------------------------------------*/ /** - @brief Dictionary object + @brief Dictionary object This object contains a list of string/string associations. Each association is identified by a unique string key. Looking up values @@ -48,16 +40,16 @@ */ /*-------------------------------------------------------------------------*/ typedef struct _dictionary_ { - int n ; /** Number of entries in dictionary */ - int size ; /** Storage size */ - char ** val ; /** List of string values */ - char ** key ; /** List of string keys */ - unsigned * hash ; /** List of hash values for keys */ + unsigned n ; /** Number of entries in dictionary */ + size_t size ; /** Storage size */ + char ** val ; /** List of string values */ + char ** key ; /** List of string keys */ + unsigned * hash ; /** List of hash values for keys */ } dictionary ; /*--------------------------------------------------------------------------- - Function prototypes + Function prototypes ---------------------------------------------------------------------------*/ /*-------------------------------------------------------------------------*/ @@ -72,20 +64,20 @@ typedef struct _dictionary_ { by comparing the key itself in last resort. */ /*--------------------------------------------------------------------------*/ -unsigned dictionary_hash(char * key); +unsigned dictionary_hash(const char * key); /*-------------------------------------------------------------------------*/ /** @brief Create a new dictionary object. @param size Optional initial size of the dictionary. - @return 1 newly allocated dictionary objet. + @return 1 newly allocated dictionary object. This function allocates a new dictionary object of given size and returns it. If you do not know in advance (roughly) the number of entries in the dictionary, give size=0. */ /*--------------------------------------------------------------------------*/ -dictionary * dictionary_new(int size); +dictionary * dictionary_new(size_t size); /*-------------------------------------------------------------------------*/ /** @@ -112,7 +104,7 @@ void dictionary_del(dictionary * vd); dictionary object, you should not try to free it or modify it. */ /*--------------------------------------------------------------------------*/ -char * dictionary_get(dictionary * d, char * key, char * def); +const char * dictionary_get(const dictionary * d, const char * key, const char * def); /*-------------------------------------------------------------------------*/ @@ -141,7 +133,7 @@ char * dictionary_get(dictionary * d, char * key, char * def); This function returns non-zero in case of failure. */ /*--------------------------------------------------------------------------*/ -int dictionary_set(dictionary * vd, char * key, char * val); +int dictionary_set(dictionary * vd, const char * key, const char * val); /*-------------------------------------------------------------------------*/ /** @@ -154,7 +146,7 @@ int dictionary_set(dictionary * vd, char * key, char * val); key cannot be found. */ /*--------------------------------------------------------------------------*/ -void dictionary_unset(dictionary * d, char * key); +void dictionary_unset(dictionary * d, const char * key); /*-------------------------------------------------------------------------*/ @@ -169,6 +161,10 @@ void dictionary_unset(dictionary * d, char * key); output file pointers. */ /*--------------------------------------------------------------------------*/ -void dictionary_dump(dictionary * d, FILE * out); +void dictionary_dump(const dictionary * d, FILE * out); + +#ifdef __cplusplus +} +#endif #endif diff --git a/include/libiniparser.h b/include/libiniparser.h index abd77aa..2fe0a3d 100644 --- a/include/libiniparser.h +++ b/include/libiniparser.h @@ -3,43 +3,23 @@ /** @file iniparser.h @author N. Devillard - @date Sep 2007 - @version 3.0 @brief Parser for ini files. */ /*--------------------------------------------------------------------------*/ -/* - $Id: iniparser.h,v 1.24 2007-11-23 21:38:19 ndevilla Exp $ - $Revision: 1.24 $ -*/ - #ifndef _INIPARSER_H_ #define _INIPARSER_H_ /*--------------------------------------------------------------------------- - Includes + Includes ---------------------------------------------------------------------------*/ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -/* - * The following #include is necessary on many Unixes but not Linux. - * It is not needed for Windows platforms. - * Uncomment it if needed. - */ -/* #include <unistd.h> */ - #include "dictionary.h" +#include <stdint.h> -/*--------------------------------------------------------------------------- - Macros - ---------------------------------------------------------------------------*/ -/** For backwards compatibility only */ -#define iniparser_getstr(d, k) iniparser_getstring(d, k, NULL) -#define iniparser_setstr iniparser_setstring +#ifdef __cplusplus +extern "C" { +#endif /*-------------------------------------------------------------------------*/ /** @@ -60,7 +40,7 @@ */ /*--------------------------------------------------------------------------*/ -int iniparser_getnsec(dictionary * d); +int iniparser_getnsec(const dictionary * d); /*-------------------------------------------------------------------------*/ @@ -78,7 +58,7 @@ int iniparser_getnsec(dictionary * d); */ /*--------------------------------------------------------------------------*/ -char * iniparser_getsecname(dictionary * d, int n); +const char * iniparser_getsecname(const dictionary * d, int n); /*-------------------------------------------------------------------------*/ @@ -86,21 +66,39 @@ char * iniparser_getsecname(dictionary * d, int n); @brief Save a dictionary to a loadable ini file @param d Dictionary to dump @param f Opened file pointer to dump to - @return void This function dumps a given dictionary into a loadable ini file. It is Ok to specify @c stderr or @c stdout as output files. + + All values are quoted, these charecters are escaped: + + - ' : the quote character (e.g. "String with \"Quotes\"") + - \ : the backslash character (e.g. "C:\\tmp") + */ /*--------------------------------------------------------------------------*/ -void iniparser_dump_ini(dictionary * d, FILE * f); +void iniparser_dump_ini(const dictionary * d, FILE * f); + +/*-------------------------------------------------------------------------*/ +/** + @brief Save a dictionary section to a loadable ini file + @param d Dictionary to dump + @param s Section name of dictionary to dump + @param f Opened file pointer to dump to + + This function dumps a given section of a given dictionary into a loadable ini + file. It is Ok to specify @c stderr or @c stdout as output files. + */ +/*--------------------------------------------------------------------------*/ + +void iniparser_dumpsection_ini(const dictionary * d, const char * s, FILE * f); /*-------------------------------------------------------------------------*/ /** @brief Dump a dictionary to an opened file pointer. @param d Dictionary to dump. @param f Opened file pointer to dump to. - @return void This function prints out the contents of a dictionary, one element by line, onto the provided file pointer. It is OK to specify @c stderr @@ -108,7 +106,7 @@ void iniparser_dump_ini(dictionary * d, FILE * f); purposes mostly. */ /*--------------------------------------------------------------------------*/ -void iniparser_dump(dictionary * d, FILE * f); +void iniparser_dump(const dictionary * d, FILE * f); /*-------------------------------------------------------------------------*/ /** @@ -125,7 +123,7 @@ void iniparser_dump(dictionary * d, FILE * f); the dictionary, do not free or modify it. */ /*--------------------------------------------------------------------------*/ -char * iniparser_getstring(dictionary * d, const char * key, char * def); +const char * iniparser_getstring(const dictionary * d, const char * key, const char * def); /*-------------------------------------------------------------------------*/ /** @@ -154,7 +152,94 @@ char * iniparser_getstring(dictionary * d, const char * key, char * def); Credits: Thanks to A. Becker for suggesting strtol() */ /*--------------------------------------------------------------------------*/ -int iniparser_getint(dictionary * d, const char * key, int notfound); +int iniparser_getint(const dictionary * d, const char * key, int notfound); + +/*-------------------------------------------------------------------------*/ +/** + @brief Get the string associated to a key, convert to an long int + @param d Dictionary to search + @param key Key string to look for + @param notfound Value to return in case of error + @return integer + + This function queries a dictionary for a key. A key as read from an + ini file is given as "section:key". If the key cannot be found, + the notfound value is returned. + + Supported values for integers include the usual C notation + so decimal, octal (starting with 0) and hexadecimal (starting with 0x) + are supported. Examples: + + - "42" -> 42 + - "042" -> 34 (octal -> decimal) + - "0x42" -> 66 (hexa -> decimal) + + Warning: the conversion may overflow in various ways. Conversion is + totally outsourced to strtol(), see the associated man page for overflow + handling. + */ +/*--------------------------------------------------------------------------*/ +long int iniparser_getlongint(const dictionary * d, const char * key, long int notfound); + +/*-------------------------------------------------------------------------*/ +/** + @brief Get the string associated to a key, convert to an int64_t + @param d Dictionary to search + @param key Key string to look for + @param notfound Value to return in case of error + @return integer + + This function queries a dictionary for a key. A key as read from an + ini file is given as "section:key". If the key cannot be found, + the notfound value is returned. + + Supported values for integers include the usual C notation + so decimal, octal (starting with 0) and hexadecimal (starting with 0x) + are supported. Examples: + + - "42" -> 42 + - "042" -> 34 (octal -> decimal) + - "0x42" -> 66 (hexa -> decimal) + + Warning: the conversion may overflow in various ways. Conversion is + totally outsourced to strtoimax(), see the associated man page for overflow + handling. + + This function is usefull on 32bit architectures where `long int` is only + 32bit. + */ +/*--------------------------------------------------------------------------*/ +int64_t iniparser_getint64(const dictionary * d, const char * key, int64_t notfound); + +/*-------------------------------------------------------------------------*/ +/** + @brief Get the string associated to a key, convert to an uint64_t + @param d Dictionary to search + @param key Key string to look for + @param notfound Value to return in case of error + @return integer + + This function queries a dictionary for a key. A key as read from an + ini file is given as "section:key". If the key cannot be found, + the notfound value is returned. + + Supported values for integers include the usual C notation + so decimal, octal (starting with 0) and hexadecimal (starting with 0x) + are supported. Examples: + + - "42" -> 42 + - "042" -> 34 (octal -> decimal) + - "0x42" -> 66 (hexa -> decimal) + + Warning: the conversion may overflow in various ways. Conversion is + totally outsourced to strtoumax(), see the associated man page for overflow + handling. + + This function is usefull on 32bit architectures where `long int` is only + 32bit. + */ +/*--------------------------------------------------------------------------*/ +uint64_t iniparser_getuint64(const dictionary * d, const char * key, uint64_t notfound); /*-------------------------------------------------------------------------*/ /** @@ -188,36 +273,18 @@ int iniparser_getint(dictionary * d, const char * key, int notfound); necessarily have to be 0 or 1. */ /*--------------------------------------------------------------------------*/ -int iniparser_getboolean(dictionary * d, const char * key, int notfound); - - -/*-------------------------------------------------------------------------*/ -/** - @brief Set an entry in a dictionary. - @param ini Dictionary to modify. - @param entry Entry to modify (entry name) - @param val New value to associate to the entry. - @return int 0 if Ok, -1 otherwise. - - If the given entry can be found in the dictionary, it is modified to - contain the provided value. If it cannot be found, -1 is returned. - It is Ok to set val to NULL. - */ -/*--------------------------------------------------------------------------*/ -int iniparser_setstring(dictionary * ini, char * entry, char * val); - +int iniparser_getboolean(const dictionary * d, const char * key, int notfound); /*-------------------------------------------------------------------------*/ /** @brief Delete an entry in a dictionary @param ini Dictionary to modify @param entry Entry to delete (entry name) - @return void If the given entry can be found, it is deleted from the dictionary. */ /*--------------------------------------------------------------------------*/ -void iniparser_unset(dictionary * ini, char * entry); +void iniparser_unset(dictionary * ini, const char * entry); /*-------------------------------------------------------------------------*/ /** @@ -231,7 +298,7 @@ void iniparser_unset(dictionary * ini, char * entry); of querying for the presence of sections in a dictionary. */ /*--------------------------------------------------------------------------*/ -int iniparser_find_entry(dictionary * ini, char * entry) ; +int iniparser_find_entry(const dictionary * ini, const char * entry) ; /*-------------------------------------------------------------------------*/ /** @@ -244,6 +311,17 @@ int iniparser_find_entry(dictionary * ini, char * entry) ; should not be accessed directly, but through accessor functions instead. + Iff the value is a quoted string it supports some escape sequences: + + - \" or ' : the quote character + (e.g. 'String with "Quotes"' or "String with 'Quotes'") + - \ : the backslash character (e.g. "C:\tmp") + + Escape sequences always start with a backslash. Additional escape sequences + might be added in the future. Backslash characters must be escaped. Any other + sequence then those outlined above is invalid and may lead to unpredictable + results. + The returned dictionary must be freed using iniparser_freedict(). */ /*--------------------------------------------------------------------------*/ @@ -251,9 +329,35 @@ dictionary * iniparser_load(const char * ininame); /*-------------------------------------------------------------------------*/ /** + @brief Parse an ini file and return an allocated dictionary object + @param in File to read. + @param ininame Name of the ini file to read (only used for nicer error messages) + @return Pointer to newly allocated dictionary + + This is the parser for ini files. This function is called, providing + the file to be read. It returns a dictionary object that should not + be accessed directly, but through accessor functions instead. + + Iff the value is a quoted string it supports some escape sequences: + + - \" or ' : the quote character + (e.g. 'String with "Quotes"' or "String with 'Quotes'") + - \ : the backslash character (e.g. "C:\tmp") + + Escape sequences always start with a backslash. Additional escape sequences + might be added in the future. Backslash characters must be escaped. Any other + sequence then those outlined above is invalid and may lead to unpredictable + results. + + The returned dictionary must be freed using iniparser_freedict(). + */ +/*--------------------------------------------------------------------------*/ +dictionary * iniparser_load_file(FILE * in, const char * ininame); + +/*-------------------------------------------------------------------------*/ +/** @brief Free all memory associated to an ini dictionary @param d Dictionary to free - @return void Free all memory associated to an ini dictionary. It is mandatory to call this function before the dictionary object @@ -262,4 +366,8 @@ dictionary * iniparser_load(const char * ininame); /*--------------------------------------------------------------------------*/ void iniparser_freedict(dictionary * d); +#ifdef __cplusplus +} +#endif + #endif diff --git a/include/libubi.h b/include/libubi.h index 8ea11e0..b5b3d8f 100644 --- a/include/libubi.h +++ b/include/libubi.h @@ -55,6 +55,7 @@ typedef void * libubi_t; * most of the users want) * @max_beb_per1024: Maximum expected bad eraseblocks per 1024 eraseblocks * @disable_fm: whether disable fastmap + * @need_resv_pool: whether reserve free pebs for filling pool/wl_pool */ struct ubi_attach_request { @@ -64,6 +65,7 @@ struct ubi_attach_request int vid_hdr_offset; int max_beb_per1024; bool disable_fm; + bool need_resv_pool; }; /** @@ -429,8 +431,8 @@ int ubi_vol_block_remove(int fd); * @bytes: how many bytes will be written to the volume * * This function initiates UBI volume update and returns %0 in case of success - * and %-1 in case of error. The caller is assumed to write @bytes data to the - * volume @fd afterward. + * and %-1 in case of error (errno is set). The caller is assumed to write + * @bytes data to the volume @fd afterward. */ int ubi_update_start(libubi_t desc, int fd, long long bytes); @@ -485,6 +487,21 @@ int ubi_leb_unmap(int fd, int lnum); */ int ubi_is_mapped(int fd, int lnum); +/** + * ubi_leb_map - map logical eraseblock to a physical eraseblock. + * @fd: volume character device file descriptor + * @lnum: logical eraseblock number + * + * This function maps an un-mapped logical eraseblock @lnum to a physical + * eraseblock. This means, that after a successful invocation of this + * function the logical eraseblock @lnum will be empty (contain only %0xFF + * bytes) and be mapped to a physical eraseblock, even if an unclean reboot + * happens. + * + * This function returns zero in case of success, %-1 in case of failures. + */ +int ubi_leb_map(int fd, int lnum); + #ifdef __cplusplus } #endif diff --git a/include/list.h b/include/list.h new file mode 100644 index 0000000..d26c9d1 --- /dev/null +++ b/include/list.h @@ -0,0 +1,263 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (c) 2006 Silicon Graphics, Inc. + * All Rights Reserved. + */ +#ifndef __LIST_H__ +#define __LIST_H__ + +#include <stddef.h> + +/* + * This undef is here because BSD 4.4 added some LIST_ macros into system + * header file sys/queue.h. This header is included in many other system + * headers and thus causes "macro redefined" warnings. + * + * As OS X is kind of a derivate of BSD, this affects OS X too. + * + * To use our own LIST_ macros (copied from kernel code), we have to + * at first undefine the conflicting system macros. + * + */ +#undef LIST_HEAD +#undef LIST_HEAD_INIT + +/* + * Simple, generic doubly-linked list implementation. + */ + +struct list_head { + struct list_head *next; + struct list_head *prev; +}; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +#define INIT_LIST_HEAD(list) list_head_init(list) +static inline void list_head_init(struct list_head *list) +{ + list->next = list->prev = list; +} + +static inline void list_head_destroy(struct list_head *list) +{ + list->next = list->prev = NULL; +} + +static inline void __list_add(struct list_head *add, + struct list_head *prev, struct list_head *next) +{ + next->prev = add; + add->next = next; + add->prev = prev; + prev->next = add; +} + +static inline void list_add(struct list_head *add, struct list_head *head) +{ + __list_add(add, head, head->next); +} + +static inline void list_add_tail(struct list_head *add, struct list_head *head) +{ + __list_add(add, head->prev, head); +} + +static inline void __list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +static inline void list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + list_head_init(entry); +} + +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); +} + +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +static inline void list_move_tail(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_is_last - tests whether @list is the last entry in list @head + * @list: the entry to test + * @head: the head of the list + */ +static inline int list_is_last(const struct list_head *list, const struct list_head *head) +{ + return list->next == head; +} + +static inline int list_empty(const struct list_head *head) +{ + return head->next == head; +} + +static inline void __list_splice(struct list_head *list, + struct list_head *prev, + struct list_head *next) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + + first->prev = prev; + prev->next = first; + + last->next = next; + next->prev = last; +} + +static inline void list_splice(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head, head->next); +} + +static inline void list_splice_tail(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head->prev, head); +} + +static inline void list_splice_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head, head->next); + list_head_init(list); + } +} + +#define list_entry(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +/** + * list_entry_is_head - test if the entry points to the head of the list + * @pos: the type * to cursor + * @head: the head for your list. + * @member: the name of the list_head within the struct. + */ +#define list_entry_is_head(pos, head, member) \ + (&pos->member == (head)) + +typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, + const struct list_head *, const struct list_head *); +__attribute__((nonnull(2,3))) +void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); + +/** + * list_splice_tail_init - join two lists and reinitialise the emptied list + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * Each of the lists is a queue. + * The list at @list is reinitialised + */ +static inline void list_splice_tail_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head->prev, head); + INIT_LIST_HEAD(list); + } +} + +/** + * list_replace - replace old entry by new one + * @old : the element to be replaced + * @new : the new element to insert + * + * If @old was empty, it will be overwritten. + */ +static inline void list_replace(struct list_head *old, + struct list_head *new) +{ + new->next = old->next; + new->next->prev = new; + new->prev = old->prev; + new->prev->next = new; +} + +/** + * list_last_entry - get the last element from a list + * @ptr: the list head to take the element from. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_head within the struct. + * + * Note, that list is expected to be not empty. + */ +#define list_last_entry(ptr, type, member) \ + list_entry((ptr)->prev, type, member) + +/** + * list_prev_entry - get the prev element in list + * @pos: the type * to cursor + * @member: the name of the list_head within the struct. + */ +#define list_prev_entry(pos, member) \ + list_entry((pos)->member.prev, typeof(*(pos)), member) + +/** + * list_next_entry - get the next element in list + * @pos: the type * to cursor + * @member: the name of the list_head within the struct. + */ +#define list_next_entry(pos, member) \ + list_entry((pos)->member.next, typeof(*(pos)), member) + +/** + * list_for_each_entry_reverse - iterate backwards over list of given type. + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the list_head within the struct. + */ +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_last_entry(head, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_prev_entry(pos, member)) + +#endif /* __LIST_H__ */ diff --git a/include/mtd/ubi-user.h b/include/mtd/ubi-user.h index a389693..bb5c0f9 100644 --- a/include/mtd/ubi-user.h +++ b/include/mtd/ubi-user.h @@ -236,6 +236,7 @@ enum { * @vid_hdr_offset: VID header offset (use defaults if %0) * @max_beb_per1024: maximum expected number of bad PEB per 1024 PEBs * @disable_fm: whether disable fastmap + * @need_resv_pool: whether reserve free pebs for filling pool/wl_pool * @padding: reserved for future, not used, has to be zeroed * * This data structure is used to specify MTD device UBI has to attach and the @@ -282,7 +283,8 @@ struct ubi_attach_req { int32_t vid_hdr_offset; int16_t max_beb_per1024; int8_t disable_fm; - int8_t padding[9]; + int8_t need_resv_pool; + int8_t padding[8]; }; /* diff --git a/include/mtd/ubifs-media.h b/include/mtd/ubifs-media.h deleted file mode 100644 index f1e3a14..0000000 --- a/include/mtd/ubifs-media.h +++ /dev/null @@ -1,869 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2006-2008 Nokia Corporation. - * - * This program is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 as published by - * the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for - * more details. - * - * You should have received a copy of the GNU General Public License along with - * this program; if not, write to the Free Software Foundation, Inc., 51 - * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - * Authors: Artem Bityutskiy (Битюцкий Артём) - * Adrian Hunter - */ - -/* - * This file describes UBIFS on-flash format and contains definitions of all the - * relevant data structures and constants. - * - * All UBIFS on-flash objects are stored in the form of nodes. All nodes start - * with the UBIFS node magic number and have the same common header. Nodes - * always sit at 8-byte aligned positions on the media and node header sizes are - * also 8-byte aligned (except for the indexing node and the padding node). - */ - -#ifndef __UBIFS_MEDIA_H__ -#define __UBIFS_MEDIA_H__ - -#include <asm/byteorder.h> - -/* UBIFS node magic number (must not have the padding byte first or last) */ -#define UBIFS_NODE_MAGIC 0x06101831 - -/* - * UBIFS on-flash format version. This version is increased when the on-flash - * format is changing. If this happens, UBIFS is will support older versions as - * well. But older UBIFS code will not support newer formats. Format changes - * will be rare and only when absolutely necessary, e.g. to fix a bug or to add - * a new feature. - * - * UBIFS went into mainline kernel with format version 4. The older formats - * were development formats. - */ -#define UBIFS_FORMAT_VERSION 5 - -/* - * Read-only compatibility version. If the UBIFS format is changed, older UBIFS - * implementations will not be able to mount newer formats in read-write mode. - * However, depending on the change, it may be possible to mount newer formats - * in R/O mode. This is indicated by the R/O compatibility version which is - * stored in the super-block. - * - * This is needed to support boot-loaders which only need R/O mounting. With - * this flag it is possible to do UBIFS format changes without a need to update - * boot-loaders. - */ -#define UBIFS_RO_COMPAT_VERSION 0 - -/* Minimum logical eraseblock size in bytes */ -#define UBIFS_MIN_LEB_SZ (15*1024) - -/* Initial CRC32 value used when calculating CRC checksums */ -#define UBIFS_CRC32_INIT 0xFFFFFFFFU - -/* - * UBIFS does not try to compress data if its length is less than the below - * constant. - */ -#define UBIFS_MIN_COMPR_LEN 128 - -/* - * If compressed data length is less than %UBIFS_MIN_COMPRESS_DIFF bytes - * shorter than uncompressed data length, UBIFS prefers to leave this data - * node uncompress, because it'll be read faster. - */ -#define UBIFS_MIN_COMPRESS_DIFF 64 - -/* Root inode number */ -#define UBIFS_ROOT_INO 1 - -/* Lowest inode number used for regular inodes (not UBIFS-only internal ones) */ -#define UBIFS_FIRST_INO 64 - -/* - * Maximum file name and extended attribute length (must be a multiple of 8, - * minus 1). - */ -#define UBIFS_MAX_NLEN 255 - -/* Maximum number of data journal heads */ -#define UBIFS_MAX_JHEADS 1 - -/* - * Size of UBIFS data block. Note, UBIFS is not a block oriented file-system, - * which means that it does not treat the underlying media as consisting of - * blocks like in case of hard drives. Do not be confused. UBIFS block is just - * the maximum amount of data which one data node can have or which can be - * attached to an inode node. - */ -#define UBIFS_BLOCK_SIZE 4096 -#define UBIFS_BLOCK_SHIFT 12 - -/* UBIFS padding byte pattern (must not be first or last byte of node magic) */ -#define UBIFS_PADDING_BYTE 0xCE - -/* Maximum possible key length */ -#define UBIFS_MAX_KEY_LEN 16 - -/* Key length ("simple" format) */ -#define UBIFS_SK_LEN 8 - -/* Minimum index tree fanout */ -#define UBIFS_MIN_FANOUT 3 - -/* Maximum number of levels in UBIFS indexing B-tree */ -#define UBIFS_MAX_LEVELS 512 - -/* Maximum amount of data attached to an inode in bytes */ -#define UBIFS_MAX_INO_DATA UBIFS_BLOCK_SIZE - -/* LEB Properties Tree fanout (must be power of 2) and fanout shift */ -#define UBIFS_LPT_FANOUT 4 -#define UBIFS_LPT_FANOUT_SHIFT 2 - -/* LEB Properties Tree bit field sizes */ -#define UBIFS_LPT_CRC_BITS 16 -#define UBIFS_LPT_CRC_BYTES 2 -#define UBIFS_LPT_TYPE_BITS 4 - -/* The key is always at the same position in all keyed nodes */ -#define UBIFS_KEY_OFFSET offsetof(struct ubifs_ino_node, key) - -/* Garbage collector journal head number */ -#define UBIFS_GC_HEAD 0 -/* Base journal head number */ -#define UBIFS_BASE_HEAD 1 -/* Data journal head number */ -#define UBIFS_DATA_HEAD 2 - -/* - * LEB Properties Tree node types. - * - * UBIFS_LPT_PNODE: LPT leaf node (contains LEB properties) - * UBIFS_LPT_NNODE: LPT internal node - * UBIFS_LPT_LTAB: LPT's own lprops table - * UBIFS_LPT_LSAVE: LPT's save table (big model only) - * UBIFS_LPT_NODE_CNT: count of LPT node types - * UBIFS_LPT_NOT_A_NODE: all ones (15 for 4 bits) is never a valid node type - */ -enum { - UBIFS_LPT_PNODE, - UBIFS_LPT_NNODE, - UBIFS_LPT_LTAB, - UBIFS_LPT_LSAVE, - UBIFS_LPT_NODE_CNT, - UBIFS_LPT_NOT_A_NODE = (1 << UBIFS_LPT_TYPE_BITS) - 1, -}; - -/* - * UBIFS inode types. - * - * UBIFS_ITYPE_REG: regular file - * UBIFS_ITYPE_DIR: directory - * UBIFS_ITYPE_LNK: soft link - * UBIFS_ITYPE_BLK: block device node - * UBIFS_ITYPE_CHR: character device node - * UBIFS_ITYPE_FIFO: fifo - * UBIFS_ITYPE_SOCK: socket - * UBIFS_ITYPES_CNT: count of supported file types - */ -enum { - UBIFS_ITYPE_REG, - UBIFS_ITYPE_DIR, - UBIFS_ITYPE_LNK, - UBIFS_ITYPE_BLK, - UBIFS_ITYPE_CHR, - UBIFS_ITYPE_FIFO, - UBIFS_ITYPE_SOCK, - UBIFS_ITYPES_CNT, -}; - -/* - * Supported key hash functions. - * - * UBIFS_KEY_HASH_R5: R5 hash - * UBIFS_KEY_HASH_TEST: test hash which just returns first 4 bytes of the name - */ -enum { - UBIFS_KEY_HASH_R5, - UBIFS_KEY_HASH_TEST, -}; - -/* - * Supported key formats. - * - * UBIFS_SIMPLE_KEY_FMT: simple key format - */ -enum { - UBIFS_SIMPLE_KEY_FMT, -}; - -/* - * The simple key format uses 29 bits for storing UBIFS block number and hash - * value. - */ -#define UBIFS_S_KEY_BLOCK_BITS 29 -#define UBIFS_S_KEY_BLOCK_MASK 0x1FFFFFFF -#define UBIFS_S_KEY_HASH_BITS UBIFS_S_KEY_BLOCK_BITS -#define UBIFS_S_KEY_HASH_MASK UBIFS_S_KEY_BLOCK_MASK - -/* - * Key types. - * - * UBIFS_INO_KEY: inode node key - * UBIFS_DATA_KEY: data node key - * UBIFS_DENT_KEY: directory entry node key - * UBIFS_XENT_KEY: extended attribute entry key - * UBIFS_KEY_TYPES_CNT: number of supported key types - */ -enum { - UBIFS_INO_KEY, - UBIFS_DATA_KEY, - UBIFS_DENT_KEY, - UBIFS_XENT_KEY, - UBIFS_KEY_TYPES_CNT, -}; - -/* Count of LEBs reserved for the superblock area */ -#define UBIFS_SB_LEBS 1 -/* Count of LEBs reserved for the master area */ -#define UBIFS_MST_LEBS 2 - -/* First LEB of the superblock area */ -#define UBIFS_SB_LNUM 0 -/* First LEB of the master area */ -#define UBIFS_MST_LNUM (UBIFS_SB_LNUM + UBIFS_SB_LEBS) -/* First LEB of the log area */ -#define UBIFS_LOG_LNUM (UBIFS_MST_LNUM + UBIFS_MST_LEBS) - -/* - * The below constants define the absolute minimum values for various UBIFS - * media areas. Many of them actually depend of flash geometry and the FS - * configuration (number of journal heads, orphan LEBs, etc). This means that - * the smallest volume size which can be used for UBIFS cannot be pre-defined - * by these constants. The file-system that meets the below limitation will not - * necessarily mount. UBIFS does run-time calculations and validates the FS - * size. - */ - -/* Minimum number of logical eraseblocks in the log */ -#define UBIFS_MIN_LOG_LEBS 2 -/* Minimum number of bud logical eraseblocks (one for each head) */ -#define UBIFS_MIN_BUD_LEBS 3 -/* Minimum number of journal logical eraseblocks */ -#define UBIFS_MIN_JNL_LEBS (UBIFS_MIN_LOG_LEBS + UBIFS_MIN_BUD_LEBS) -/* Minimum number of LPT area logical eraseblocks */ -#define UBIFS_MIN_LPT_LEBS 2 -/* Minimum number of orphan area logical eraseblocks */ -#define UBIFS_MIN_ORPH_LEBS 1 -/* - * Minimum number of main area logical eraseblocks (buds, 3 for the index, 1 - * for GC, 1 for deletions, and at least 1 for committed data). - */ -#define UBIFS_MIN_MAIN_LEBS (UBIFS_MIN_BUD_LEBS + 6) - -/* Minimum number of logical eraseblocks */ -#define UBIFS_MIN_LEB_CNT (UBIFS_SB_LEBS + UBIFS_MST_LEBS + \ - UBIFS_MIN_LOG_LEBS + UBIFS_MIN_LPT_LEBS + \ - UBIFS_MIN_ORPH_LEBS + UBIFS_MIN_MAIN_LEBS) - -/* Node sizes (N.B. these are guaranteed to be multiples of 8) */ -#define UBIFS_CH_SZ sizeof(struct ubifs_ch) -#define UBIFS_INO_NODE_SZ sizeof(struct ubifs_ino_node) -#define UBIFS_DATA_NODE_SZ sizeof(struct ubifs_data_node) -#define UBIFS_DENT_NODE_SZ sizeof(struct ubifs_dent_node) -#define UBIFS_TRUN_NODE_SZ sizeof(struct ubifs_trun_node) -#define UBIFS_PAD_NODE_SZ sizeof(struct ubifs_pad_node) -#define UBIFS_SB_NODE_SZ sizeof(struct ubifs_sb_node) -#define UBIFS_MST_NODE_SZ sizeof(struct ubifs_mst_node) -#define UBIFS_REF_NODE_SZ sizeof(struct ubifs_ref_node) -#define UBIFS_IDX_NODE_SZ sizeof(struct ubifs_idx_node) -#define UBIFS_CS_NODE_SZ sizeof(struct ubifs_cs_node) -#define UBIFS_ORPH_NODE_SZ sizeof(struct ubifs_orph_node) -#define UBIFS_AUTH_NODE_SZ sizeof(struct ubifs_auth_node) -#define UBIFS_SIG_NODE_SZ sizeof(struct ubifs_sig_node) - -/* Extended attribute entry nodes are identical to directory entry nodes */ -#define UBIFS_XENT_NODE_SZ UBIFS_DENT_NODE_SZ -/* Only this does not have to be multiple of 8 bytes */ -#define UBIFS_BRANCH_SZ sizeof(struct ubifs_branch) - -/* Maximum node sizes (N.B. these are guaranteed to be multiples of 8) */ -#define UBIFS_MAX_DATA_NODE_SZ (UBIFS_DATA_NODE_SZ + UBIFS_BLOCK_SIZE) -#define UBIFS_MAX_INO_NODE_SZ (UBIFS_INO_NODE_SZ + UBIFS_MAX_INO_DATA) -#define UBIFS_MAX_DENT_NODE_SZ (UBIFS_DENT_NODE_SZ + UBIFS_MAX_NLEN + 1) -#define UBIFS_MAX_XENT_NODE_SZ UBIFS_MAX_DENT_NODE_SZ - -/* The largest UBIFS node */ -#define UBIFS_MAX_NODE_SZ UBIFS_MAX_INO_NODE_SZ - -/* The maxmimum size of a hash, enough for sha512 */ -#define UBIFS_MAX_HASH_LEN 64 - -/* The maxmimum size of a hmac, enough for hmac(sha512) */ -#define UBIFS_MAX_HMAC_LEN 64 - -/* - * xattr name of UBIFS encryption context, we don't use a prefix - * nor a long name to not waste space on the flash. - */ -#define UBIFS_XATTR_NAME_ENCRYPTION_CONTEXT "c" - -/* Type field in ubifs_sig_node */ -#define UBIFS_SIGNATURE_TYPE_PKCS7 1 - -/* - * On-flash inode flags. - * - * UBIFS_COMPR_FL: use compression for this inode - * UBIFS_SYNC_FL: I/O on this inode has to be synchronous - * UBIFS_IMMUTABLE_FL: inode is immutable - * UBIFS_APPEND_FL: writes to the inode may only append data - * UBIFS_DIRSYNC_FL: I/O on this directory inode has to be synchronous - * UBIFS_XATTR_FL: this inode is the inode for an extended attribute value - * UBIFS_CRYPT_FL: use encryption for this inode - * - * Note, these are on-flash flags which correspond to ioctl flags - * (@FS_COMPR_FL, etc). They have the same values now, but generally, do not - * have to be the same. - */ -enum { - UBIFS_COMPR_FL = 0x01, - UBIFS_SYNC_FL = 0x02, - UBIFS_IMMUTABLE_FL = 0x04, - UBIFS_APPEND_FL = 0x08, - UBIFS_DIRSYNC_FL = 0x10, - UBIFS_XATTR_FL = 0x20, - UBIFS_CRYPT_FL = 0x40, -}; - -/* Inode flag bits used by UBIFS */ -#define UBIFS_FL_MASK 0x0000001F - -/* - * UBIFS compression algorithms. - * - * UBIFS_COMPR_NONE: no compression - * UBIFS_COMPR_LZO: LZO compression - * UBIFS_COMPR_ZLIB: ZLIB compression - * UBIFS_COMPR_ZSTD: ZSTD compression - * UBIFS_COMPR_TYPES_CNT: count of supported compression types - */ -enum { - UBIFS_COMPR_NONE, - UBIFS_COMPR_LZO, - UBIFS_COMPR_ZLIB, - UBIFS_COMPR_ZSTD, - UBIFS_COMPR_TYPES_CNT, -}; - -/* - * UBIFS node types. - * - * UBIFS_INO_NODE: inode node - * UBIFS_DATA_NODE: data node - * UBIFS_DENT_NODE: directory entry node - * UBIFS_XENT_NODE: extended attribute node - * UBIFS_TRUN_NODE: truncation node - * UBIFS_PAD_NODE: padding node - * UBIFS_SB_NODE: superblock node - * UBIFS_MST_NODE: master node - * UBIFS_REF_NODE: LEB reference node - * UBIFS_IDX_NODE: index node - * UBIFS_CS_NODE: commit start node - * UBIFS_ORPH_NODE: orphan node - * UBIFS_AUTH_NODE: authentication node - * UBIFS_SIG_NODE: signature node - * UBIFS_NODE_TYPES_CNT: count of supported node types - * - * Note, we index arrays by these numbers, so keep them low and contiguous. - * Node type constants for inodes, direntries and so on have to be the same as - * corresponding key type constants. - */ -enum { - UBIFS_INO_NODE, - UBIFS_DATA_NODE, - UBIFS_DENT_NODE, - UBIFS_XENT_NODE, - UBIFS_TRUN_NODE, - UBIFS_PAD_NODE, - UBIFS_SB_NODE, - UBIFS_MST_NODE, - UBIFS_REF_NODE, - UBIFS_IDX_NODE, - UBIFS_CS_NODE, - UBIFS_ORPH_NODE, - UBIFS_AUTH_NODE, - UBIFS_SIG_NODE, - UBIFS_NODE_TYPES_CNT, -}; - -/* - * Master node flags. - * - * UBIFS_MST_DIRTY: rebooted uncleanly - master node is dirty - * UBIFS_MST_NO_ORPHS: no orphan inodes present - * UBIFS_MST_RCVRY: written by recovery - */ -enum { - UBIFS_MST_DIRTY = 1, - UBIFS_MST_NO_ORPHS = 2, - UBIFS_MST_RCVRY = 4, -}; - -/* - * Node group type (used by recovery to recover whole group or none). - * - * UBIFS_NO_NODE_GROUP: this node is not part of a group - * UBIFS_IN_NODE_GROUP: this node is a part of a group - * UBIFS_LAST_OF_NODE_GROUP: this node is the last in a group - */ -enum { - UBIFS_NO_NODE_GROUP = 0, - UBIFS_IN_NODE_GROUP, - UBIFS_LAST_OF_NODE_GROUP, -}; - -/* - * Superblock flags. - * - * UBIFS_FLG_BIGLPT: if "big" LPT model is used if set - * UBIFS_FLG_SPACE_FIXUP: first-mount "fixup" of free space within LEBs needed - * UBIFS_FLG_DOUBLE_HASH: store a 32bit cookie in directory entry nodes to - * support 64bit cookies for lookups by hash - * UBIFS_FLG_ENCRYPTION: this filesystem contains encrypted files - * UBIFS_FLG_AUTHENTICATION: this filesystem contains hashes for authentication - */ -enum { - UBIFS_FLG_BIGLPT = 0x02, - UBIFS_FLG_SPACE_FIXUP = 0x04, - UBIFS_FLG_DOUBLE_HASH = 0x08, - UBIFS_FLG_ENCRYPTION = 0x10, - UBIFS_FLG_AUTHENTICATION = 0x20, -}; - -#define UBIFS_FLG_MASK (UBIFS_FLG_BIGLPT | UBIFS_FLG_SPACE_FIXUP | \ - UBIFS_FLG_DOUBLE_HASH | UBIFS_FLG_ENCRYPTION | \ - UBIFS_FLG_AUTHENTICATION) - -/** - * struct ubifs_ch - common header node. - * @magic: UBIFS node magic number (%UBIFS_NODE_MAGIC) - * @crc: CRC-32 checksum of the node header - * @sqnum: sequence number - * @len: full node length - * @node_type: node type - * @group_type: node group type - * @padding: reserved for future, zeroes - * - * Every UBIFS node starts with this common part. If the node has a key, the - * key always goes next. - */ -struct ubifs_ch { - __le32 magic; - __le32 crc; - __le64 sqnum; - __le32 len; - __u8 node_type; - __u8 group_type; - __u8 padding[2]; -} __attribute__ ((packed)); - -/** - * union ubifs_dev_desc - device node descriptor. - * @new: new type device descriptor - * @huge: huge type device descriptor - * - * This data structure describes major/minor numbers of a device node. In an - * inode is a device node then its data contains an object of this type. UBIFS - * uses standard Linux "new" and "huge" device node encodings. - */ -union ubifs_dev_desc { - __le32 new; - __le64 huge; -} __attribute__ ((packed)); - -/** - * struct ubifs_ino_node - inode node. - * @ch: common header - * @key: node key - * @creat_sqnum: sequence number at time of creation - * @size: inode size in bytes (amount of uncompressed data) - * @atime_sec: access time seconds - * @ctime_sec: creation time seconds - * @mtime_sec: modification time seconds - * @atime_nsec: access time nanoseconds - * @ctime_nsec: creation time nanoseconds - * @mtime_nsec: modification time nanoseconds - * @nlink: number of hard links - * @uid: owner ID - * @gid: group ID - * @mode: access flags - * @flags: per-inode flags (%UBIFS_COMPR_FL, %UBIFS_SYNC_FL, etc) - * @data_len: inode data length - * @xattr_cnt: count of extended attributes this inode has - * @xattr_size: summarized size of all extended attributes in bytes - * @padding1: reserved for future, zeroes - * @xattr_names: sum of lengths of all extended attribute names belonging to - * this inode - * @compr_type: compression type used for this inode - * @padding2: reserved for future, zeroes - * @data: data attached to the inode - * - * Note, even though inode compression type is defined by @compr_type, some - * nodes of this inode may be compressed with different compressor - this - * happens if compression type is changed while the inode already has data - * nodes. But @compr_type will be use for further writes to the inode. - * - * Note, do not forget to amend 'zero_ino_node_unused()' function when changing - * the padding fields. - */ -struct ubifs_ino_node { - struct ubifs_ch ch; - __u8 key[UBIFS_MAX_KEY_LEN]; - __le64 creat_sqnum; - __le64 size; - __le64 atime_sec; - __le64 ctime_sec; - __le64 mtime_sec; - __le32 atime_nsec; - __le32 ctime_nsec; - __le32 mtime_nsec; - __le32 nlink; - __le32 uid; - __le32 gid; - __le32 mode; - __le32 flags; - __le32 data_len; - __le32 xattr_cnt; - __le32 xattr_size; - __u8 padding1[4]; /* Watch 'zero_ino_node_unused()' if changing! */ - __le32 xattr_names; - __le16 compr_type; - __u8 padding2[26]; /* Watch 'zero_ino_node_unused()' if changing! */ - __u8 data[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_dent_node - directory entry node. - * @ch: common header - * @key: node key - * @inum: target inode number - * @padding1: reserved for future, zeroes - * @type: type of the target inode (%UBIFS_ITYPE_REG, %UBIFS_ITYPE_DIR, etc) - * @nlen: name length - * @cookie: A 32bits random number, used to construct a 64bits - * identifier. - * @name: zero-terminated name - * - * Note, do not forget to amend 'zero_dent_node_unused()' function when - * changing the padding fields. - */ -struct ubifs_dent_node { - struct ubifs_ch ch; - __u8 key[UBIFS_MAX_KEY_LEN]; - __le64 inum; - __u8 padding1; - __u8 type; - __le16 nlen; - __le32 cookie; - __u8 name[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_data_node - data node. - * @ch: common header - * @key: node key - * @size: uncompressed data size in bytes - * @compr_type: compression type (%UBIFS_COMPR_NONE, %UBIFS_COMPR_LZO, etc) - * @compr_size: compressed data size in bytes, only valid when data is encrypted - * @data: data - * - */ -struct ubifs_data_node { - struct ubifs_ch ch; - __u8 key[UBIFS_MAX_KEY_LEN]; - __le32 size; - __le16 compr_type; - __le16 compr_size; - __u8 data[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_trun_node - truncation node. - * @ch: common header - * @inum: truncated inode number - * @padding: reserved for future, zeroes - * @old_size: size before truncation - * @new_size: size after truncation - * - * This node exists only in the journal and never goes to the main area. Note, - * do not forget to amend 'zero_trun_node_unused()' function when changing the - * padding fields. - */ -struct ubifs_trun_node { - struct ubifs_ch ch; - __le32 inum; - __u8 padding[12]; /* Watch 'zero_trun_node_unused()' if changing! */ - __le64 old_size; - __le64 new_size; -} __attribute__ ((packed)); - -/** - * struct ubifs_pad_node - padding node. - * @ch: common header - * @pad_len: how many bytes after this node are unused (because padded) - * @padding: reserved for future, zeroes - */ -struct ubifs_pad_node { - struct ubifs_ch ch; - __le32 pad_len; -} __attribute__ ((packed)); - -/** - * struct ubifs_sb_node - superblock node. - * @ch: common header - * @padding: reserved for future, zeroes - * @key_hash: type of hash function used in keys - * @key_fmt: format of the key - * @flags: file-system flags (%UBIFS_FLG_BIGLPT, etc) - * @min_io_size: minimal input/output unit size - * @leb_size: logical eraseblock size in bytes - * @leb_cnt: count of LEBs used by file-system - * @max_leb_cnt: maximum count of LEBs used by file-system - * @max_bud_bytes: maximum amount of data stored in buds - * @log_lebs: log size in logical eraseblocks - * @lpt_lebs: number of LEBs used for lprops table - * @orph_lebs: number of LEBs used for recording orphans - * @jhead_cnt: count of journal heads - * @fanout: tree fanout (max. number of links per indexing node) - * @lsave_cnt: number of LEB numbers in LPT's save table - * @fmt_version: UBIFS on-flash format version - * @default_compr: default compression algorithm (%UBIFS_COMPR_LZO, etc) - * @padding1: reserved for future, zeroes - * @rp_uid: reserve pool UID - * @rp_gid: reserve pool GID - * @rp_size: size of the reserved pool in bytes - * @padding2: reserved for future, zeroes - * @time_gran: time granularity in nanoseconds - * @uuid: UUID generated when the file system image was created - * @ro_compat_version: UBIFS R/O compatibility version - * @hmac: HMAC to authenticate the superblock node - * @hmac_wkm: HMAC of a well known message (the string "UBIFS") as a convenience - * to the user to check if the correct key is passed. - * @hash_algo: The hash algo used for this filesystem (one of enum hash_algo) - * @hash_mst: hash of the master node, only valid for signed images in which the - * master node does not contain a hmac - */ -struct ubifs_sb_node { - struct ubifs_ch ch; - __u8 padding[2]; - __u8 key_hash; - __u8 key_fmt; - __le32 flags; - __le32 min_io_size; - __le32 leb_size; - __le32 leb_cnt; - __le32 max_leb_cnt; - __le64 max_bud_bytes; - __le32 log_lebs; - __le32 lpt_lebs; - __le32 orph_lebs; - __le32 jhead_cnt; - __le32 fanout; - __le32 lsave_cnt; - __le32 fmt_version; - __le16 default_compr; - __u8 padding1[2]; - __le32 rp_uid; - __le32 rp_gid; - __le64 rp_size; - __le32 time_gran; - __u8 uuid[16]; - __le32 ro_compat_version; - __u8 hmac[UBIFS_MAX_HMAC_LEN]; - __u8 hmac_wkm[UBIFS_MAX_HMAC_LEN]; - __le16 hash_algo; - __u8 hash_mst[UBIFS_MAX_HASH_LEN]; - __u8 padding2[3774]; -} __attribute__ ((packed)); - -/** - * struct ubifs_mst_node - master node. - * @ch: common header - * @highest_inum: highest inode number in the committed index - * @cmt_no: commit number - * @flags: various flags (%UBIFS_MST_DIRTY, etc) - * @log_lnum: start of the log - * @root_lnum: LEB number of the root indexing node - * @root_offs: offset within @root_lnum - * @root_len: root indexing node length - * @gc_lnum: LEB reserved for garbage collection (%-1 value means the LEB was - * not reserved and should be reserved on mount) - * @ihead_lnum: LEB number of index head - * @ihead_offs: offset of index head - * @index_size: size of index on flash - * @total_free: total free space in bytes - * @total_dirty: total dirty space in bytes - * @total_used: total used space in bytes (includes only data LEBs) - * @total_dead: total dead space in bytes (includes only data LEBs) - * @total_dark: total dark space in bytes (includes only data LEBs) - * @lpt_lnum: LEB number of LPT root nnode - * @lpt_offs: offset of LPT root nnode - * @nhead_lnum: LEB number of LPT head - * @nhead_offs: offset of LPT head - * @ltab_lnum: LEB number of LPT's own lprops table - * @ltab_offs: offset of LPT's own lprops table - * @lsave_lnum: LEB number of LPT's save table (big model only) - * @lsave_offs: offset of LPT's save table (big model only) - * @lscan_lnum: LEB number of last LPT scan - * @empty_lebs: number of empty logical eraseblocks - * @idx_lebs: number of indexing logical eraseblocks - * @leb_cnt: count of LEBs used by file-system - * @hash_root_idx: the hash of the root index node - * @hash_lpt: the hash of the LPT - * @hmac: HMAC to authenticate the master node - * @padding: reserved for future, zeroes - */ -struct ubifs_mst_node { - struct ubifs_ch ch; - __le64 highest_inum; - __le64 cmt_no; - __le32 flags; - __le32 log_lnum; - __le32 root_lnum; - __le32 root_offs; - __le32 root_len; - __le32 gc_lnum; - __le32 ihead_lnum; - __le32 ihead_offs; - __le64 index_size; - __le64 total_free; - __le64 total_dirty; - __le64 total_used; - __le64 total_dead; - __le64 total_dark; - __le32 lpt_lnum; - __le32 lpt_offs; - __le32 nhead_lnum; - __le32 nhead_offs; - __le32 ltab_lnum; - __le32 ltab_offs; - __le32 lsave_lnum; - __le32 lsave_offs; - __le32 lscan_lnum; - __le32 empty_lebs; - __le32 idx_lebs; - __le32 leb_cnt; - __u8 hash_root_idx[UBIFS_MAX_HASH_LEN]; - __u8 hash_lpt[UBIFS_MAX_HASH_LEN]; - __u8 hmac[UBIFS_MAX_HMAC_LEN]; - __u8 padding[152]; -} __attribute__ ((packed)); - -/** - * struct ubifs_ref_node - logical eraseblock reference node. - * @ch: common header - * @lnum: the referred logical eraseblock number - * @offs: start offset in the referred LEB - * @jhead: journal head number - * @padding: reserved for future, zeroes - */ -struct ubifs_ref_node { - struct ubifs_ch ch; - __le32 lnum; - __le32 offs; - __le32 jhead; - __u8 padding[28]; -} __attribute__ ((packed)); - -/** - * struct ubifs_auth_node - node for authenticating other nodes - * @ch: common header - * @hmac: The HMAC - */ -struct ubifs_auth_node { - struct ubifs_ch ch; - __u8 hmac[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_sig_node - node for signing other nodes - * @ch: common header - * @type: type of the signature, currently only UBIFS_SIGNATURE_TYPE_PKCS7 - * supported - * @len: The length of the signature data - * @padding: reserved for future, zeroes - * @sig: The signature data - */ -struct ubifs_sig_node { - struct ubifs_ch ch; - __le32 type; - __le32 len; - __u8 padding[32]; - __u8 sig[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_branch - key/reference/length branch - * @lnum: LEB number of the target node - * @offs: offset within @lnum - * @len: target node length - * @key: key - * - * In an authenticated UBIFS we have the hash of the referenced node after @key. - * This can't be added to the struct type definition because @key is a - * dynamically sized element already. - */ -struct ubifs_branch { - __le32 lnum; - __le32 offs; - __le32 len; - __u8 key[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_idx_node - indexing node. - * @ch: common header - * @child_cnt: number of child index nodes - * @level: tree level - * @branches: LEB number / offset / length / key branches - */ -struct ubifs_idx_node { - struct ubifs_ch ch; - __le16 child_cnt; - __le16 level; - __u8 branches[]; -} __attribute__ ((packed)); - -/** - * struct ubifs_cs_node - commit start node. - * @ch: common header - * @cmt_no: commit number - */ -struct ubifs_cs_node { - struct ubifs_ch ch; - __le64 cmt_no; -} __attribute__ ((packed)); - -/** - * struct ubifs_orph_node - orphan node. - * @ch: common header - * @cmt_no: commit number (also top bit is set on the last node of the commit) - * @inos: inode numbers of orphans - */ -struct ubifs_orph_node { - struct ubifs_ch ch; - __le64 cmt_no; - __le64 inos[]; -} __attribute__ ((packed)); - -#endif /* __UBIFS_MEDIA_H__ */ diff --git a/include/rbtree.h b/include/rbtree.h new file mode 100644 index 0000000..89926e7 --- /dev/null +++ b/include/rbtree.h @@ -0,0 +1,203 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <andrea@suse.de> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include <linux/kernel.h> +#include <linux/stddef.h> + +struct rb_node +{ + unsigned long rb_parent_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root +{ + struct rb_node *rb_node; +}; + + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) +#define rb_color(r) ((r)->rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; +} + +#define RB_ROOT (struct rb_root) { NULL, } + +/* Newer gcc versions take care of exporting this */ +#ifndef offsetof +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) +#endif + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) +#define RB_EMPTY_NODE(node) (rb_parent(node) == node) +#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_last(struct rb_root *); + +/* Postorder iteration - always visit the parent after its children */ +extern struct rb_node *rb_first_postorder(const struct rb_root *); +extern struct rb_node *rb_next_postorder(const struct rb_node *); + +#define rb_entry_safe(ptr, type, member) \ + ({ typeof(ptr) ____ptr = (ptr); \ + ____ptr ? rb_entry(____ptr, type, member) : NULL; \ + }) + +/** + * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of + * given type allowing the backing memory of @pos to be invalidated + * + * @pos: the 'type *' to use as a loop cursor. + * @n: another 'type *' to use as temporary storage + * @root: 'rb_root *' of the rbtree. + * @field: the name of the rb_node field within 'type'. + * + * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as + * list_for_each_entry_safe() and allows the iteration to continue independent + * of changes to @pos by the body of the loop. + * + * Note, however, that it cannot handle other modifications that re-order the + * rbtree it is iterating over. This includes calling rb_erase() on @pos, as + * rb_erase() may rebalance the tree, causing us to miss some nodes. + */ +#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ + for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \ + pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \ + typeof(*pos), field); 1; }); \ + pos = n) + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->rb_parent_color = (unsigned long )parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ |