From 7d81790ced345585b1e647ca9d0f6678e7062fa4 Mon Sep 17 00:00:00 2001 From: Dongsheng Yang Date: Sat, 31 Oct 2015 11:12:01 +0800 Subject: mtd-utils: Restructure the mtd-utils source. * There is no code modification in this commit, only moving * the files to proper place. The user tools looks a little messy as we place almost the all tools in the root directory of mtd-utils. To make it more clear, I propose to introduce the following structure for our source code. mtd-utils/ |-- lib |-- include |-- misc-utils |-- jffsX-utils |-- nand-utils |-- nor-utils |-- ubi-utils |-- ubifs-utils `-- tests Signed-off-by: Dongsheng Yang Signed-off-by: Brian Norris --- mkfs.ubifs/.gitignore | 1 - mkfs.ubifs/COPYING | 340 ----- mkfs.ubifs/README | 9 - mkfs.ubifs/compr.c | 219 --- mkfs.ubifs/compr.h | 46 - mkfs.ubifs/crc16.c | 56 - mkfs.ubifs/crc16.h | 27 - mkfs.ubifs/defs.h | 92 -- mkfs.ubifs/devtable.c | 524 ------- mkfs.ubifs/hashtable/hashtable.c | 277 ---- mkfs.ubifs/hashtable/hashtable.h | 199 --- mkfs.ubifs/hashtable/hashtable_itr.c | 176 --- mkfs.ubifs/hashtable/hashtable_itr.h | 112 -- mkfs.ubifs/hashtable/hashtable_private.h | 85 -- mkfs.ubifs/key.h | 189 --- mkfs.ubifs/lpt.c | 578 -------- mkfs.ubifs/lpt.h | 28 - mkfs.ubifs/mkfs.ubifs.c | 2324 ------------------------------ mkfs.ubifs/mkfs.ubifs.h | 150 -- mkfs.ubifs/ubifs.h | 441 ------ 20 files changed, 5873 deletions(-) delete mode 100644 mkfs.ubifs/.gitignore delete mode 100644 mkfs.ubifs/COPYING delete mode 100644 mkfs.ubifs/README delete mode 100644 mkfs.ubifs/compr.c delete mode 100644 mkfs.ubifs/compr.h delete mode 100644 mkfs.ubifs/crc16.c delete mode 100644 mkfs.ubifs/crc16.h delete mode 100644 mkfs.ubifs/defs.h delete mode 100644 mkfs.ubifs/devtable.c delete mode 100644 mkfs.ubifs/hashtable/hashtable.c delete mode 100644 mkfs.ubifs/hashtable/hashtable.h delete mode 100644 mkfs.ubifs/hashtable/hashtable_itr.c delete mode 100644 mkfs.ubifs/hashtable/hashtable_itr.h delete mode 100644 mkfs.ubifs/hashtable/hashtable_private.h delete mode 100644 mkfs.ubifs/key.h delete mode 100644 mkfs.ubifs/lpt.c delete mode 100644 mkfs.ubifs/lpt.h delete mode 100644 mkfs.ubifs/mkfs.ubifs.c delete mode 100644 mkfs.ubifs/mkfs.ubifs.h delete mode 100644 mkfs.ubifs/ubifs.h (limited to 'mkfs.ubifs') diff --git a/mkfs.ubifs/.gitignore b/mkfs.ubifs/.gitignore deleted file mode 100644 index 6b0e85c..0000000 --- a/mkfs.ubifs/.gitignore +++ /dev/null @@ -1 +0,0 @@ -/mkfs.ubifs diff --git a/mkfs.ubifs/COPYING b/mkfs.ubifs/COPYING deleted file mode 100644 index 60549be..0000000 --- a/mkfs.ubifs/COPYING +++ /dev/null @@ -1,340 +0,0 @@ - GNU GENERAL PUBLIC LICENSE - Version 2, June 1991 - - Copyright (C) 1989, 1991 Free Software Foundation, Inc. - 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - Everyone is permitted to copy and distribute verbatim copies - of this license document, but changing it is not allowed. - - Preamble - - The licenses for most software are designed to take away your -freedom to share and change it. By contrast, the GNU General Public -License is intended to guarantee your freedom to share and change free -software--to make sure the software is free for all its users. This -General Public License applies to most of the Free Software -Foundation's software and to any other program whose authors commit to -using it. (Some other Free Software Foundation software is covered by -the GNU Library General Public License instead.) You can apply it to -your programs, too. - - When we speak of free software, we are referring to freedom, not -price. Our General Public Licenses are designed to make sure that you -have the freedom to distribute copies of free software (and charge for -this service if you wish), that you receive source code or can get it -if you want it, that you can change the software or use pieces of it -in new free programs; and that you know you can do these things. - - To protect your rights, we need to make restrictions that forbid -anyone to deny you these rights or to ask you to surrender the rights. -These restrictions translate to certain responsibilities for you if you -distribute copies of the software, or if you modify it. - - For example, if you distribute copies of such a program, whether -gratis or for a fee, you must give the recipients all the rights that -you have. You must make sure that they, too, receive or can get the -source code. And you must show them these terms so they know their -rights. - - We protect your rights with two steps: (1) copyright the software, and -(2) offer you this license which gives you legal permission to copy, -distribute and/or modify the software. - - Also, for each author's protection and ours, we want to make certain -that everyone understands that there is no warranty for this free -software. If the software is modified by someone else and passed on, we -want its recipients to know that what they have is not the original, so -that any problems introduced by others will not reflect on the original -authors' reputations. - - Finally, any free program is threatened constantly by software -patents. We wish to avoid the danger that redistributors of a free -program will individually obtain patent licenses, in effect making the -program proprietary. To prevent this, we have made it clear that any -patent must be licensed for everyone's free use or not licensed at all. - - The precise terms and conditions for copying, distribution and -modification follow. - - GNU GENERAL PUBLIC LICENSE - TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION - - 0. This License applies to any program or other work which contains -a notice placed by the copyright holder saying it may be distributed -under the terms of this General Public License. The "Program", below, -refers to any such program or work, and a "work based on the Program" -means either the Program or any derivative work under copyright law: -that is to say, a work containing the Program or a portion of it, -either verbatim or with modifications and/or translated into another -language. (Hereinafter, translation is included without limitation in -the term "modification".) Each licensee is addressed as "you". - -Activities other than copying, distribution and modification are not -covered by this License; they are outside its scope. The act of -running the Program is not restricted, and the output from the Program -is covered only if its contents constitute a work based on the -Program (independent of having been made by running the Program). -Whether that is true depends on what the Program does. - - 1. You may copy and distribute verbatim copies of the Program's -source code as you receive it, in any medium, provided that you -conspicuously and appropriately publish on each copy an appropriate -copyright notice and disclaimer of warranty; keep intact all the -notices that refer to this License and to the absence of any warranty; -and give any other recipients of the Program a copy of this License -along with the Program. - -You may charge a fee for the physical act of transferring a copy, and -you may at your option offer warranty protection in exchange for a fee. - - 2. You may modify your copy or copies of the Program or any portion -of it, thus forming a work based on the Program, and copy and -distribute such modifications or work under the terms of Section 1 -above, provided that you also meet all of these conditions: - - a) You must cause the modified files to carry prominent notices - stating that you changed the files and the date of any change. - - b) You must cause any work that you distribute or publish, that in - whole or in part contains or is derived from the Program or any - part thereof, to be licensed as a whole at no charge to all third - parties under the terms of this License. - - c) If the modified program normally reads commands interactively - when run, you must cause it, when started running for such - interactive use in the most ordinary way, to print or display an - announcement including an appropriate copyright notice and a - notice that there is no warranty (or else, saying that you provide - a warranty) and that users may redistribute the program under - these conditions, and telling the user how to view a copy of this - License. (Exception: if the Program itself is interactive but - does not normally print such an announcement, your work based on - the Program is not required to print an announcement.) - -These requirements apply to the modified work as a whole. If -identifiable sections of that work are not derived from the Program, -and can be reasonably considered independent and separate works in -themselves, then this License, and its terms, do not apply to those -sections when you distribute them as separate works. But when you -distribute the same sections as part of a whole which is a work based -on the Program, the distribution of the whole must be on the terms of -this License, whose permissions for other licensees extend to the -entire whole, and thus to each and every part regardless of who wrote it. - -Thus, it is not the intent of this section to claim rights or contest -your rights to work written entirely by you; rather, the intent is to -exercise the right to control the distribution of derivative or -collective works based on the Program. - -In addition, mere aggregation of another work not based on the Program -with the Program (or with a work based on the Program) on a volume of -a storage or distribution medium does not bring the other work under -the scope of this License. - - 3. You may copy and distribute the Program (or a work based on it, -under Section 2) in object code or executable form under the terms of -Sections 1 and 2 above provided that you also do one of the following: - - a) Accompany it with the complete corresponding machine-readable - source code, which must be distributed under the terms of Sections - 1 and 2 above on a medium customarily used for software interchange; or, - - b) Accompany it with a written offer, valid for at least three - years, to give any third party, for a charge no more than your - cost of physically performing source distribution, a complete - machine-readable copy of the corresponding source code, to be - distributed under the terms of Sections 1 and 2 above on a medium - customarily used for software interchange; or, - - c) Accompany it with the information you received as to the offer - to distribute corresponding source code. (This alternative is - allowed only for noncommercial distribution and only if you - received the program in object code or executable form with such - an offer, in accord with Subsection b above.) - -The source code for a work means the preferred form of the work for -making modifications to it. For an executable work, complete source -code means all the source code for all modules it contains, plus any -associated interface definition files, plus the scripts used to -control compilation and installation of the executable. However, as a -special exception, the source code distributed need not include -anything that is normally distributed (in either source or binary -form) with the major components (compiler, kernel, and so on) of the -operating system on which the executable runs, unless that component -itself accompanies the executable. - -If distribution of executable or object code is made by offering -access to copy from a designated place, then offering equivalent -access to copy the source code from the same place counts as -distribution of the source code, even though third parties are not -compelled to copy the source along with the object code. - - 4. You may not copy, modify, sublicense, or distribute the Program -except as expressly provided under this License. Any attempt -otherwise to copy, modify, sublicense or distribute the Program is -void, and will automatically terminate your rights under this License. -However, parties who have received copies, or rights, from you under -this License will not have their licenses terminated so long as such -parties remain in full compliance. - - 5. You are not required to accept this License, since you have not -signed it. However, nothing else grants you permission to modify or -distribute the Program or its derivative works. These actions are -prohibited by law if you do not accept this License. Therefore, by -modifying or distributing the Program (or any work based on the -Program), you indicate your acceptance of this License to do so, and -all its terms and conditions for copying, distributing or modifying -the Program or works based on it. - - 6. Each time you redistribute the Program (or any work based on the -Program), the recipient automatically receives a license from the -original licensor to copy, distribute or modify the Program subject to -these terms and conditions. You may not impose any further -restrictions on the recipients' exercise of the rights granted herein. -You are not responsible for enforcing compliance by third parties to -this License. - - 7. If, as a consequence of a court judgment or allegation of patent -infringement or for any other reason (not limited to patent issues), -conditions are imposed on you (whether by court order, agreement or -otherwise) that contradict the conditions of this License, they do not -excuse you from the conditions of this License. If you cannot -distribute so as to satisfy simultaneously your obligations under this -License and any other pertinent obligations, then as a consequence you -may not distribute the Program at all. For example, if a patent -license would not permit royalty-free redistribution of the Program by -all those who receive copies directly or indirectly through you, then -the only way you could satisfy both it and this License would be to -refrain entirely from distribution of the Program. - -If any portion of this section is held invalid or unenforceable under -any particular circumstance, the balance of the section is intended to -apply and the section as a whole is intended to apply in other -circumstances. - -It is not the purpose of this section to induce you to infringe any -patents or other property right claims or to contest validity of any -such claims; this section has the sole purpose of protecting the -integrity of the free software distribution system, which is -implemented by public license practices. Many people have made -generous contributions to the wide range of software distributed -through that system in reliance on consistent application of that -system; it is up to the author/donor to decide if he or she is willing -to distribute software through any other system and a licensee cannot -impose that choice. - -This section is intended to make thoroughly clear what is believed to -be a consequence of the rest of this License. - - 8. If the distribution and/or use of the Program is restricted in -certain countries either by patents or by copyrighted interfaces, the -original copyright holder who places the Program under this License -may add an explicit geographical distribution limitation excluding -those countries, so that distribution is permitted only in or among -countries not thus excluded. In such case, this License incorporates -the limitation as if written in the body of this License. - - 9. The Free Software Foundation may publish revised and/or new versions -of the General Public License from time to time. Such new versions will -be similar in spirit to the present version, but may differ in detail to -address new problems or concerns. - -Each version is given a distinguishing version number. If the Program -specifies a version number of this License which applies to it and "any -later version", you have the option of following the terms and conditions -either of that version or of any later version published by the Free -Software Foundation. If the Program does not specify a version number of -this License, you may choose any version ever published by the Free Software -Foundation. - - 10. If you wish to incorporate parts of the Program into other free -programs whose distribution conditions are different, write to the author -to ask for permission. For software which is copyrighted by the Free -Software Foundation, write to the Free Software Foundation; we sometimes -make exceptions for this. Our decision will be guided by the two goals -of preserving the free status of all derivatives of our free software and -of promoting the sharing and reuse of software generally. - - NO WARRANTY - - 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY -FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN -OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES -PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED -OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF -MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS -TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE -PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, -REPAIR OR CORRECTION. - - 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING -WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR -REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, -INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING -OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED -TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY -YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER -PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE -POSSIBILITY OF SUCH DAMAGES. - - END OF TERMS AND CONDITIONS - - How to Apply These Terms to Your New Programs - - If you develop a new program, and you want it to be of the greatest -possible use to the public, the best way to achieve this is to make it -free software which everyone can redistribute and change under these terms. - - To do so, attach the following notices to the program. It is safest -to attach them to the start of each source file to most effectively -convey the exclusion of warranty; and each file should have at least -the "copyright" line and a pointer to where the full notice is found. - - - Copyright (C) 19yy - - 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 - - -Also add information on how to contact you by electronic and paper mail. - -If the program is interactive, make it output a short notice like this -when it starts in an interactive mode: - - Gnomovision version 69, Copyright (C) 19yy name of author - Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. - This is free software, and you are welcome to redistribute it - under certain conditions; type `show c' for details. - -The hypothetical commands `show w' and `show c' should show the appropriate -parts of the General Public License. Of course, the commands you use may -be called something other than `show w' and `show c'; they could even be -mouse-clicks or menu items--whatever suits your program. - -You should also get your employer (if you work as a programmer) or your -school, if any, to sign a "copyright disclaimer" for the program, if -necessary. Here is a sample; alter the names: - - Yoyodyne, Inc., hereby disclaims all copyright interest in the program - `Gnomovision' (which makes passes at compilers) written by James Hacker. - - , 1 April 1989 - Ty Coon, President of Vice - -This General Public License does not permit incorporating your program into -proprietary programs. If your program is a subroutine library, you may -consider it more useful to permit linking proprietary applications with the -library. If this is what you want to do, use the GNU Library General -Public License instead of this License. diff --git a/mkfs.ubifs/README b/mkfs.ubifs/README deleted file mode 100644 index 7e19939..0000000 --- a/mkfs.ubifs/README +++ /dev/null @@ -1,9 +0,0 @@ -UBIFS File System - Make File System program - -* crc16.h and crc16.c were copied from the linux kernel. -* crc32.h and crc32.c were copied from mtd-utils and amended. -* ubifs.h is a selection of definitions from fs/ubifs/ubifs.h from the linux kernel. -* key.h is copied from fs/ubifs/key.h from the linux kernel. -* defs.h is a bunch of definitions to smooth things over. -* lpt.c is a selection of functions copied from fs/ubifs/lpt.c from the linux kernel, and amended. -* hashtable/* was downloaded from http://www.cl.cam.ac.uk/~cwc22/hashtable/ diff --git a/mkfs.ubifs/compr.c b/mkfs.ubifs/compr.c deleted file mode 100644 index 34b2f60..0000000 --- a/mkfs.ubifs/compr.c +++ /dev/null @@ -1,219 +0,0 @@ -/* - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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 - * Zoltan Sogor - */ - -#include -#include -#include -#include -#include -#include - -#define crc32 __zlib_crc32 -#include -#undef crc32 - -#include "compr.h" -#include "mkfs.ubifs.h" - -static void *lzo_mem; -static unsigned long long errcnt = 0; -static struct ubifs_info *c = &info_; - -#define DEFLATE_DEF_LEVEL Z_DEFAULT_COMPRESSION -#define DEFLATE_DEF_WINBITS 11 -#define DEFLATE_DEF_MEMLEVEL 8 - -static int zlib_deflate(void *in_buf, size_t in_len, void *out_buf, - size_t *out_len) -{ - z_stream strm; - - strm.zalloc = NULL; - strm.zfree = NULL; - - /* - * Match exactly the zlib parameters used by the Linux kernel crypto - * API. - */ - if (deflateInit2(&strm, DEFLATE_DEF_LEVEL, Z_DEFLATED, - -DEFLATE_DEF_WINBITS, DEFLATE_DEF_MEMLEVEL, - Z_DEFAULT_STRATEGY)) { - errcnt += 1; - return -1; - } - - strm.next_in = in_buf; - strm.avail_in = in_len; - strm.total_in = 0; - - strm.next_out = out_buf; - strm.avail_out = *out_len; - strm.total_out = 0; - - if (deflate(&strm, Z_FINISH) != Z_STREAM_END) { - deflateEnd(&strm); - errcnt += 1; - return -1; - } - - if (deflateEnd(&strm) != Z_OK) { - errcnt += 1; - return -1; - } - - *out_len = strm.total_out; - - return 0; -} - -static int lzo_compress(void *in_buf, size_t in_len, void *out_buf, - size_t *out_len) -{ - lzo_uint len; - int ret; - - len = *out_len; - ret = lzo1x_999_compress(in_buf, in_len, out_buf, &len, lzo_mem); - *out_len = len; - - if (ret != LZO_E_OK) { - errcnt += 1; - return -1; - } - - return 0; -} - -static int no_compress(void *in_buf, size_t in_len, void *out_buf, - size_t *out_len) -{ - memcpy(out_buf, in_buf, in_len); - *out_len = in_len; - return 0; -} - -static char *zlib_buf; - -static int favor_lzo_compress(void *in_buf, size_t in_len, void *out_buf, - size_t *out_len, int *type) -{ - int lzo_ret, zlib_ret; - size_t lzo_len, zlib_len; - - lzo_len = zlib_len = *out_len; - lzo_ret = lzo_compress(in_buf, in_len, out_buf, &lzo_len); - zlib_ret = zlib_deflate(in_buf, in_len, zlib_buf, &zlib_len); - - if (lzo_ret && zlib_ret) - /* Both compressors failed */ - return -1; - - if (!lzo_ret && !zlib_ret) { - double percent; - - /* Both compressors succeeded */ - if (lzo_len <= zlib_len ) - goto select_lzo; - - percent = (double)zlib_len / (double)lzo_len; - percent *= 100; - if (percent > 100 - c->favor_percent) - goto select_lzo; - goto select_zlib; - } - - if (lzo_ret) - /* Only zlib compressor succeeded */ - goto select_zlib; - - /* Only LZO compressor succeeded */ - -select_lzo: - *out_len = lzo_len; - *type = MKFS_UBIFS_COMPR_LZO; - return 0; - -select_zlib: - *out_len = zlib_len; - *type = MKFS_UBIFS_COMPR_ZLIB; - memcpy(out_buf, zlib_buf, zlib_len); - return 0; -} - -int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len, - int type) -{ - int ret; - - if (in_len < UBIFS_MIN_COMPR_LEN) { - no_compress(in_buf, in_len, out_buf, out_len); - return MKFS_UBIFS_COMPR_NONE; - } - - if (c->favor_lzo) - ret = favor_lzo_compress(in_buf, in_len, out_buf, out_len, &type); - else { - switch (type) { - case MKFS_UBIFS_COMPR_LZO: - ret = lzo_compress(in_buf, in_len, out_buf, out_len); - break; - case MKFS_UBIFS_COMPR_ZLIB: - ret = zlib_deflate(in_buf, in_len, out_buf, out_len); - break; - case MKFS_UBIFS_COMPR_NONE: - ret = 1; - break; - default: - errcnt += 1; - ret = 1; - break; - } - } - if (ret || *out_len >= in_len) { - no_compress(in_buf, in_len, out_buf, out_len); - return MKFS_UBIFS_COMPR_NONE; - } - return type; -} - -int init_compression(void) -{ - lzo_mem = malloc(LZO1X_999_MEM_COMPRESS); - if (!lzo_mem) - return -1; - - zlib_buf = malloc(UBIFS_BLOCK_SIZE * WORST_COMPR_FACTOR); - if (!zlib_buf) { - free(lzo_mem); - return -1; - } - - return 0; -} - -void destroy_compression(void) -{ - free(zlib_buf); - free(lzo_mem); - if (errcnt) - fprintf(stderr, "%llu compression errors occurred\n", errcnt); -} diff --git a/mkfs.ubifs/compr.h b/mkfs.ubifs/compr.h deleted file mode 100644 index e3dd95c..0000000 --- a/mkfs.ubifs/compr.h +++ /dev/null @@ -1,46 +0,0 @@ -/* - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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 - * Zoltan Sogor - */ - -#ifndef __UBIFS_COMPRESS_H__ -#define __UBIFS_COMPRESS_H__ - -/* - * Compressors may end-up with more data in the output buffer than in the input - * buffer. This constant defined the worst case factor, i.e. we assume that the - * output buffer may be at max. WORST_COMPR_FACTOR times larger than input - * buffer. - */ -#define WORST_COMPR_FACTOR 4 - -enum compression_type -{ - MKFS_UBIFS_COMPR_NONE, - MKFS_UBIFS_COMPR_LZO, - MKFS_UBIFS_COMPR_ZLIB, -}; - -int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len, - int type); -int init_compression(void); -void destroy_compression(void); - -#endif diff --git a/mkfs.ubifs/crc16.c b/mkfs.ubifs/crc16.c deleted file mode 100644 index a19512e..0000000 --- a/mkfs.ubifs/crc16.c +++ /dev/null @@ -1,56 +0,0 @@ -/* - * This code was taken from the linux kernel. The license is GPL Version 2. - */ - -#include "crc16.h" - -/** CRC table for the CRC-16. The poly is 0x8005 (x^16 + x^15 + x^2 + 1) */ -uint16_t const crc16_table[256] = { - 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, - 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440, - 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, - 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841, - 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40, - 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41, - 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641, - 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040, - 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, - 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441, - 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, - 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840, - 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, - 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40, - 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640, - 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041, - 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240, - 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441, - 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, - 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840, - 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, - 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40, - 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640, - 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041, - 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241, - 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440, - 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, - 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841, - 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, - 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41, - 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, - 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040 -}; - -/** - * crc16 - compute the CRC-16 for the data buffer - * @crc: previous CRC value - * @buffer: data pointer - * @len: number of bytes in the buffer - * - * Returns the updated CRC value. - */ -uint16_t crc16(uint16_t crc, uint8_t const *buffer, size_t len) -{ - while (len--) - crc = crc16_byte(crc, *buffer++); - return crc; -} diff --git a/mkfs.ubifs/crc16.h b/mkfs.ubifs/crc16.h deleted file mode 100644 index 539d21a..0000000 --- a/mkfs.ubifs/crc16.h +++ /dev/null @@ -1,27 +0,0 @@ -/* - * Implements the standard CRC-16: - * Width 16 - * Poly 0x8005 (x^16 + x^15 + x^2 + 1) - * Init 0 - * - * Copyright (c) 2005 Ben Gardner - * - * This code was taken from the linux kernel. The license is GPL Version 2. - */ - -#ifndef __CRC16_H__ -#define __CRC16_H__ - -#include -#include - -extern uint16_t const crc16_table[256]; - -extern uint16_t crc16(uint16_t crc, const uint8_t *buffer, size_t len); - -static inline uint16_t crc16_byte(uint16_t crc, const uint8_t data) -{ - return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff]; -} - -#endif /* __CRC16_H__ */ diff --git a/mkfs.ubifs/defs.h b/mkfs.ubifs/defs.h deleted file mode 100644 index 1fa3316..0000000 --- a/mkfs.ubifs/defs.h +++ /dev/null @@ -1,92 +0,0 @@ -/* - * Greate deal of the code was taken from the kernel UBIFS implementation, and - * this file contains some "glue" definitions. - */ - -#ifndef __UBIFS_DEFS_H__ -#define __UBIFS_DEFS_H__ - -#define t16(x) ({ \ - uint16_t __b = (x); \ - (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_16(__b); \ -}) - -#define t32(x) ({ \ - uint32_t __b = (x); \ - (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_32(__b); \ -}) - -#define t64(x) ({ \ - uint64_t __b = (x); \ - (__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_64(__b); \ -}) - -#define cpu_to_le16(x) ((__le16){t16(x)}) -#define cpu_to_le32(x) ((__le32){t32(x)}) -#define cpu_to_le64(x) ((__le64){t64(x)}) - -#define le16_to_cpu(x) (t16((x))) -#define le32_to_cpu(x) (t32((x))) -#define le64_to_cpu(x) (t64((x))) - -#define unlikely(x) (x) - -#define ubifs_assert(x) ({}) - -struct qstr -{ - char *name; - size_t len; -}; - -/** - * fls - find last (most-significant) bit set - * @x: the word to search - * - * This is defined the same way as ffs. - * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. - */ -static inline int fls(int x) -{ - int r = 32; - - if (!x) - return 0; - if (!(x & 0xffff0000u)) { - x <<= 16; - r -= 16; - } - if (!(x & 0xff000000u)) { - x <<= 8; - r -= 8; - } - if (!(x & 0xf0000000u)) { - x <<= 4; - r -= 4; - } - if (!(x & 0xc0000000u)) { - x <<= 2; - r -= 2; - } - if (!(x & 0x80000000u)) { - x <<= 1; - r -= 1; - } - return r; -} - -#define do_div(n,base) ({ \ -int __res; \ -__res = ((unsigned long) n) % (unsigned) base; \ -n = ((unsigned long) n) / (unsigned) base; \ -__res; }) - -#if INT_MAX != 0x7fffffff -#error : sizeof(int) must be 4 for this program -#endif - -#if (~0ULL) != 0xffffffffffffffffULL -#error : sizeof(long long) must be 8 for this program -#endif - -#endif diff --git a/mkfs.ubifs/devtable.c b/mkfs.ubifs/devtable.c deleted file mode 100644 index dee035d..0000000 --- a/mkfs.ubifs/devtable.c +++ /dev/null @@ -1,524 +0,0 @@ -/* - * Copyright (C) 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 - * - * Author: Artem Bityutskiy - * - * Part of the device table parsing code was taken from the mkfs.jffs2 utility. - * The original author of that code is Erik Andersen, hence: - * Copyright (C) 2001, 2002 Erik Andersen - */ - -/* - * This file implemented device table support. Device table entries take the - * form of: - * - * /dev/mem c 640 0 0 1 1 0 0 - - * - * Type can be one of: - * f A regular file - * d Directory - * c Character special device file - * b Block special device file - * p Fifo (named pipe) - * - * Don't bother with symlinks (permissions are irrelevant), hard links (special - * cases of regular files), or sockets (why bother). - * - * Regular files must exist in the target root directory. If a char, block, - * fifo, or directory does not exist, it will be created. - * - * Please, refer the device_table.txt file which can be found at MTD utilities - * for more information about what the device table is. - */ - -#include "mkfs.ubifs.h" -#include "hashtable/hashtable.h" -#include "hashtable/hashtable_itr.h" - -/* - * The hash table which contains paths to files/directories/device nodes - * referred to in the device table. For example, if the device table refers - * "/dev/loop0", the @path_htbl will contain "/dev" element. - */ -static struct hashtable *path_htbl; - -/* Hash function used for hash tables */ -static unsigned int r5_hash(void *s) -{ - unsigned int a = 0; - const signed char *str = s; - - while (*str) { - a += *str << 4; - a += *str >> 4; - a *= 11; - str++; - } - - return a; -} - -/* - * Check whether 2 keys of a hash table are equivalent. The keys are path/file - * names, so we simply use 'strcmp()'. - */ -static int is_equivalent(void *k1, void *k2) -{ - return !strcmp(k1, k2); -} - -/** - * separate_last - separate out the last path component - * @buf: the path to split - * @len: length of the @buf string - * @path: the beginning of path is returned here - * @name: the last path component is returned here - * - * This helper function separates out the the last component of the full path - * string. For example, "/dev/loop" would be split on "/dev" and "loop". This - * function allocates memory for @path and @name and return the result there. - * Returns zero in case of success and a negative error code in case of - * failure. - */ -static int separate_last(const char *buf, int len, char **path, char **name) -{ - int path_len = len, name_len; - const char *p = buf + len, *n; - - while (*--p != '/') - path_len -= 1; - - /* Drop the final '/' unless this is the root directory */ - name_len = len - path_len; - n = buf + path_len; - if (path_len > 1) - path_len -= 1; - - *path = malloc(path_len + 1); - if (!*path) - return err_msg("cannot allocate %d bytes of memory", - path_len + 1); - memcpy(*path, buf, path_len); - (*path)[path_len] = '\0'; - - *name = malloc(name_len + 1); - if (!*name) { - free(*path); - return err_msg("cannot allocate %d bytes of memory", - name_len + 1); - } - memcpy(*name, n, name_len + 1); - - return 0; -} - -static int interpret_table_entry(const char *line) -{ - char buf[1024], type, *path = NULL, *name = NULL; - int len; - struct path_htbl_element *ph_elt = NULL; - struct name_htbl_element *nh_elt = NULL; - unsigned int mode = 0755, uid = 0, gid = 0, major = 0, minor = 0; - unsigned int start = 0, increment = 0, count = 0; - - if (sscanf(line, "%1023s %c %o %u %u %u %u %u %u %u", - buf, &type, &mode, &uid, &gid, &major, &minor, - &start, &increment, &count) < 0) - return sys_err_msg("sscanf failed"); - - dbg_msg(3, "name %s, type %c, mode %o, uid %u, gid %u, major %u, " - "minor %u, start %u, inc %u, cnt %u", - buf, type, mode, uid, gid, major, minor, start, - increment, count); - - len = strnlen(buf, 1024); - if (len == 1024) - return err_msg("too long path"); - - if (!strcmp(buf, "/")) - return err_msg("device table entries require absolute paths"); - if (buf[1] == '\0') - return err_msg("root directory cannot be created"); - if (strstr(buf, "//")) - return err_msg("'//' cannot be used in the path"); - if (buf[len - 1] == '/') - return err_msg("do not put '/' at the end"); - - if (strstr(buf, "/./") || strstr(buf, "/../") || - !strcmp(buf + len - 2, "/.") || !strcmp(buf + len - 3, "/..")) - return err_msg("'.' and '..' cannot be used in the path"); - - switch (type) { - case 'd': - mode |= S_IFDIR; - break; - case 'f': - mode |= S_IFREG; - break; - case 'p': - mode |= S_IFIFO; - break; - case 'c': - mode |= S_IFCHR; - break; - case 'b': - mode |= S_IFBLK; - break; - default: - return err_msg("unsupported file type '%c'", type); - } - - if (separate_last(buf, len, &path, &name)) - return -1; - - /* - * Check if this path already exist in the path hash table and add it - * if it is not. - */ - ph_elt = hashtable_search(path_htbl, path); - if (!ph_elt) { - dbg_msg(3, "inserting '%s' into path hash table", path); - ph_elt = malloc(sizeof(struct path_htbl_element)); - if (!ph_elt) { - err_msg("cannot allocate %zd bytes of memory", - sizeof(struct path_htbl_element)); - goto out_free; - } - - if (!hashtable_insert(path_htbl, path, ph_elt)) { - err_msg("cannot insert into path hash table"); - goto out_free; - } - - ph_elt->path = path; - path = NULL; - ph_elt->name_htbl = create_hashtable(128, &r5_hash, - &is_equivalent); - if (!ph_elt->name_htbl) { - err_msg("cannot create name hash table"); - goto out_free; - } - } - - if (increment != 0 && count == 0) - return err_msg("count cannot be zero if increment is non-zero"); - - /* - * Add the file/directory/device node (last component of the path) to - * the name hashtable. The name hashtable resides in the corresponding - * path hashtable element. - */ - - if (count == 0) { - /* This entry does not require any iterating */ - nh_elt = malloc(sizeof(struct name_htbl_element)); - if (!nh_elt) { - err_msg("cannot allocate %zd bytes of memory", - sizeof(struct name_htbl_element)); - goto out_free; - } - - nh_elt->mode = mode; - nh_elt->uid = uid; - nh_elt->gid = gid; - nh_elt->dev = makedev(major, minor); - - dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", - name, major(nh_elt->dev), minor(nh_elt->dev)); - - if (hashtable_search(ph_elt->name_htbl, name)) - return err_msg("'%s' is referred twice", buf); - - nh_elt->name = name; - if (!hashtable_insert(ph_elt->name_htbl, name, nh_elt)) { - err_msg("cannot insert into name hash table"); - goto out_free; - } - } else { - int i, num = start + count, len = strlen(name) + 20; - char *nm; - - for (i = start; i < num; i++) { - nh_elt = malloc(sizeof(struct name_htbl_element)); - if (!nh_elt) { - err_msg("cannot allocate %zd bytes of memory", - sizeof(struct name_htbl_element)); - goto out_free; - } - - nh_elt->mode = mode; - nh_elt->uid = uid; - nh_elt->gid = gid; - nh_elt->dev = makedev(major, minor + (i - start) * increment); - - nm = malloc(len); - if (!nm) { - err_msg("cannot allocate %d bytes of memory", len); - goto out_free; - } - - sprintf(nm, "%s%d", name, i); - nh_elt->name = nm; - - dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)", - nm, major(nh_elt->dev), minor(nh_elt->dev)); - - if (hashtable_search(ph_elt->name_htbl, nm)) { - err_msg("'%s' is referred twice", buf); - free (nm); - goto out_free; - } - - if (!hashtable_insert(ph_elt->name_htbl, nm, nh_elt)) { - err_msg("cannot insert into name hash table"); - free (nm); - goto out_free; - } - } - free(name); - name = NULL; - } - - return 0; - -out_free: - free(ph_elt); - free(nh_elt); - free(path); - free(name); - return -1; -} - -/** - * parse_devtable - parse the device table. - * @tbl_file: device table file name - * - * This function parses the device table and prepare the hash table which will - * later be used by mkfs.ubifs to create the specified files/device nodes. - * Returns zero in case of success and a negative error code in case of - * failure. - */ -int parse_devtable(const char *tbl_file) -{ - FILE *f; - char *line = NULL; - struct stat st; - size_t len; - - dbg_msg(1, "parsing device table file '%s'", tbl_file); - - path_htbl = create_hashtable(128, &r5_hash, &is_equivalent); - if (!path_htbl) - return err_msg("cannot create path hash table"); - - f = fopen(tbl_file, "r"); - if (!f) - return sys_err_msg("cannot open '%s'", tbl_file); - - if (fstat(fileno(f), &st) < 0) { - sys_err_msg("cannot stat '%s'", tbl_file); - goto out_close; - } - - if (st.st_size < 10) { - sys_err_msg("'%s' is too short", tbl_file); - goto out_close; - } - - /* - * The general plan now is to read in one line at a time, check for - * leading comment delimiters ('#'), then try and parse the line as a - * device table - */ - while (getline(&line, &len, f) != -1) { - /* First trim off any white-space */ - len = strlen(line); - - /* Trim trailing white-space */ - while (len > 0 && isspace(line[len - 1])) - line[--len] = '\0'; - /* Trim leading white-space */ - memmove(line, &line[strspn(line, " \n\r\t\v")], len); - - /* How long are we after trimming? */ - len = strlen(line); - - /* If this is not a comment line, try to interpret it */ - if (len && *line != '#') { - if (interpret_table_entry(line)) { - err_msg("cannot parse '%s'", line); - goto out_close; - } - } - - free(line); - line = NULL; - } - - dbg_msg(1, "finished parsing"); - fclose(f); - return 0; - -out_close: - fclose(f); - free_devtable_info(); - return -1; -} - -/** - * devtbl_find_path - find a path in the path hash table. - * @path: UBIFS path to find. - * - * This looks up the path hash table. Returns the path hash table element - * reference if @path was found and %NULL if not. - */ -struct path_htbl_element *devtbl_find_path(const char *path) -{ - if (!path_htbl) - return NULL; - - return hashtable_search(path_htbl, (void *)path); -} - -/** - * devtbl_find_name - find a name in the name hash table. - * @ph_etl: path hash table element to find at - * @name: name to find - * - * This looks up the name hash table. Returns the name hash table element - * reference if @name found and %NULL if not. - */ -struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt, - const char *name) -{ - if (!path_htbl) - return NULL; - - return hashtable_search(ph_elt->name_htbl, (void *)name); -} - -/** - * override_attributes - override inode attributes. - * @st: struct stat object to containing the attributes to override - * @ph_elt: path hash table element object - * @nh_elt: name hash table element object containing the new values - * - * The device table file may override attributes like UID of files. For - * example, the device table may contain a "/dev" entry, and the UBIFS FS on - * the host may contain "/dev" directory. In this case the attributes of the - * "/dev" directory inode has to be as the device table specifies. - * - * Note, the hash element is removed by this function as well. - */ -int override_attributes(struct stat *st, struct path_htbl_element *ph_elt, - struct name_htbl_element *nh_elt) -{ - if (!path_htbl) - return 0; - - if (S_ISCHR(st->st_mode) || S_ISBLK(st->st_mode) || - S_ISFIFO(st->st_mode)) - return err_msg("%s/%s both exists at UBIFS root at host, " - "and is referred from the device table", - strcmp(ph_elt->path, "/") ? ph_elt->path : "", - nh_elt->name); - - if ((st->st_mode & S_IFMT) != (nh_elt->mode & S_IFMT)) - return err_msg("%s/%s is referred from the device table also exists in " - "the UBIFS root directory at host, but the file type is " - "different", strcmp(ph_elt->path, "/") ? ph_elt->path : "", - nh_elt->name); - - dbg_msg(3, "set UID %d, GID %d, mode %o for %s/%s as device table says", - nh_elt->uid, nh_elt->gid, nh_elt->mode, ph_elt->path, nh_elt->name); - - st->st_uid = nh_elt->uid; - st->st_gid = nh_elt->gid; - st->st_mode = nh_elt->mode; - - hashtable_remove(ph_elt->name_htbl, (void *)nh_elt->name); - return 0; -} - -/** - * first_name_htbl_element - return first element of the name hash table. - * @ph_elt: the path hash table the name hash table belongs to - * @itr: double pointer to a 'struct hashtable_itr' object where the - * information about further iterations is stored - * - * This function implements name hash table iteration together with - * 'next_name_htbl_element()'. Returns the first name hash table element or - * %NULL if the hash table is empty. - */ -struct name_htbl_element * -first_name_htbl_element(struct path_htbl_element *ph_elt, - struct hashtable_itr **itr) -{ - if (!path_htbl || !ph_elt || hashtable_count(ph_elt->name_htbl) == 0) - return NULL; - - *itr = hashtable_iterator(ph_elt->name_htbl); - return hashtable_iterator_value(*itr); -} - -/** - * first_name_htbl_element - return next element of the name hash table. - * @ph_elt: the path hash table the name hash table belongs to - * @itr: double pointer to a 'struct hashtable_itr' object where the - * information about further iterations is stored - * - * This function implements name hash table iteration together with - * 'first_name_htbl_element()'. Returns the next name hash table element or - * %NULL if there are no more elements. - */ -struct name_htbl_element * -next_name_htbl_element(struct path_htbl_element *ph_elt, - struct hashtable_itr **itr) -{ - if (!path_htbl || !ph_elt || !hashtable_iterator_advance(*itr)) - return NULL; - - return hashtable_iterator_value(*itr); -} - -/** - * free_devtable_info - free device table information. - * - * This function frees the path hash table and the name hash tables. - */ -void free_devtable_info(void) -{ - struct hashtable_itr *ph_itr; - struct path_htbl_element *ph_elt; - - if (!path_htbl) - return; - - if (hashtable_count(path_htbl) > 0) { - ph_itr = hashtable_iterator(path_htbl); - do { - ph_elt = hashtable_iterator_value(ph_itr); - /* - * Note, since we use the same string for the key and - * @name in the name hash table elements, we do not - * have to iterate name hash table because @name memory - * will be freed when freeing the key. - */ - hashtable_destroy(ph_elt->name_htbl, 1); - } while (hashtable_iterator_advance(ph_itr)); - } - hashtable_destroy(path_htbl, 1); -} diff --git a/mkfs.ubifs/hashtable/hashtable.c b/mkfs.ubifs/hashtable/hashtable.c deleted file mode 100644 index c1f99ed..0000000 --- a/mkfs.ubifs/hashtable/hashtable.c +++ /dev/null @@ -1,277 +0,0 @@ -/* Copyright (C) 2004 Christopher Clark */ - -#define PROGRAM_NAME "hashtable" - -#include "common.h" -#include "hashtable.h" -#include "hashtable_private.h" -#include -#include -#include -#include - -/* -Credit for primes table: Aaron Krowne - http://br.endernet.org/~akrowne/ - http://planetmath.org/encyclopedia/GoodHashTablePrimes.html -*/ -static const unsigned int primes[] = { -53, 97, 193, 389, -769, 1543, 3079, 6151, -12289, 24593, 49157, 98317, -196613, 393241, 786433, 1572869, -3145739, 6291469, 12582917, 25165843, -50331653, 100663319, 201326611, 402653189, -805306457, 1610612741 -}; -const unsigned int prime_table_length = ARRAY_SIZE(primes); -const float max_load_factor = 0.65; - -/*****************************************************************************/ -struct hashtable * -create_hashtable(unsigned int minsize, - unsigned int (*hashf) (void*), - int (*eqf) (void*,void*)) -{ - struct hashtable *h; - unsigned int pindex, size = primes[0]; - /* Check requested hashtable isn't too large */ - if (minsize > (1u << 30)) return NULL; - /* Enforce size as prime */ - for (pindex=0; pindex < prime_table_length; pindex++) { - if (primes[pindex] > minsize) { size = primes[pindex]; break; } - } - h = (struct hashtable *)malloc(sizeof(struct hashtable)); - if (NULL == h) return NULL; /*oom*/ - h->table = (struct entry **)malloc(sizeof(struct entry*) * size); - if (NULL == h->table) { free(h); return NULL; } /*oom*/ - memset(h->table, 0, size * sizeof(struct entry *)); - h->tablelength = size; - h->primeindex = pindex; - h->entrycount = 0; - h->hashfn = hashf; - h->eqfn = eqf; - h->loadlimit = (unsigned int) ceil(size * max_load_factor); - return h; -} - -/*****************************************************************************/ -unsigned int -hash(struct hashtable *h, void *k) -{ - /* Aim to protect against poor hash functions by adding logic here - * - logic taken from java 1.4 hashtable source */ - unsigned int i = h->hashfn(k); - i += ~(i << 9); - i ^= ((i >> 14) | (i << 18)); /* >>> */ - i += (i << 4); - i ^= ((i >> 10) | (i << 22)); /* >>> */ - return i; -} - -/*****************************************************************************/ -static int -hashtable_expand(struct hashtable *h) -{ - /* Double the size of the table to accomodate more entries */ - struct entry **newtable; - struct entry *e; - struct entry **pE; - unsigned int newsize, i, index; - /* Check we're not hitting max capacity */ - if (h->primeindex == (prime_table_length - 1)) return 0; - newsize = primes[++(h->primeindex)]; - - newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize); - if (NULL != newtable) - { - memset(newtable, 0, newsize * sizeof(struct entry *)); - /* This algorithm is not 'stable'. ie. it reverses the list - * when it transfers entries between the tables */ - for (i = 0; i < h->tablelength; i++) { - while (NULL != (e = h->table[i])) { - h->table[i] = e->next; - index = indexFor(newsize,e->h); - e->next = newtable[index]; - newtable[index] = e; - } - } - free(h->table); - h->table = newtable; - } - /* Plan B: realloc instead */ - else - { - newtable = (struct entry **) - realloc(h->table, newsize * sizeof(struct entry *)); - if (NULL == newtable) { (h->primeindex)--; return 0; } - h->table = newtable; - memset(newtable[h->tablelength], 0, newsize - h->tablelength); - for (i = 0; i < h->tablelength; i++) { - for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) { - index = indexFor(newsize,e->h); - if (index == i) - { - pE = &(e->next); - } - else - { - *pE = e->next; - e->next = newtable[index]; - newtable[index] = e; - } - } - } - } - h->tablelength = newsize; - h->loadlimit = (unsigned int) ceil(newsize * max_load_factor); - return -1; -} - -/*****************************************************************************/ -unsigned int -hashtable_count(struct hashtable *h) -{ - return h->entrycount; -} - -/*****************************************************************************/ -int -hashtable_insert(struct hashtable *h, void *k, void *v) -{ - /* This method allows duplicate keys - but they shouldn't be used */ - unsigned int index; - struct entry *e; - if (++(h->entrycount) > h->loadlimit) - { - /* Ignore the return value. If expand fails, we should - * still try cramming just this value into the existing table - * -- we may not have memory for a larger table, but one more - * element may be ok. Next time we insert, we'll try expanding again.*/ - hashtable_expand(h); - } - e = (struct entry *)malloc(sizeof(struct entry)); - if (NULL == e) { --(h->entrycount); return 0; } /*oom*/ - e->h = hash(h,k); - index = indexFor(h->tablelength,e->h); - e->k = k; - e->v = v; - e->next = h->table[index]; - h->table[index] = e; - return -1; -} - -/*****************************************************************************/ -void * /* returns value associated with key */ -hashtable_search(struct hashtable *h, void *k) -{ - struct entry *e; - unsigned int hashvalue, index; - hashvalue = hash(h,k); - index = indexFor(h->tablelength,hashvalue); - e = h->table[index]; - while (NULL != e) - { - /* Check hash value to short circuit heavier comparison */ - if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v; - e = e->next; - } - return NULL; -} - -/*****************************************************************************/ -void * /* returns value associated with key */ -hashtable_remove(struct hashtable *h, void *k) -{ - /* TODO: consider compacting the table when the load factor drops enough, - * or provide a 'compact' method. */ - - struct entry *e; - struct entry **pE; - void *v; - unsigned int hashvalue, index; - - hashvalue = hash(h,k); - index = indexFor(h->tablelength,hash(h,k)); - pE = &(h->table[index]); - e = *pE; - while (NULL != e) - { - /* Check hash value to short circuit heavier comparison */ - if ((hashvalue == e->h) && (h->eqfn(k, e->k))) - { - *pE = e->next; - h->entrycount--; - v = e->v; - freekey(e->k); - free(e); - return v; - } - pE = &(e->next); - e = e->next; - } - return NULL; -} - -/*****************************************************************************/ -/* destroy */ -void -hashtable_destroy(struct hashtable *h, int free_values) -{ - unsigned int i; - struct entry *e, *f; - struct entry **table = h->table; - if (free_values) - { - for (i = 0; i < h->tablelength; i++) - { - e = table[i]; - while (NULL != e) - { f = e; e = e->next; freekey(f->k); free(f->v); free(f); } - } - } - else - { - for (i = 0; i < h->tablelength; i++) - { - e = table[i]; - while (NULL != e) - { f = e; e = e->next; freekey(f->k); free(f); } - } - } - free(h->table); - free(h); -} - -/* - * Copyright (c) 2002, Christopher Clark - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * * Neither the name of the original author; nor the names of any contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ diff --git a/mkfs.ubifs/hashtable/hashtable.h b/mkfs.ubifs/hashtable/hashtable.h deleted file mode 100644 index c0b0acd..0000000 --- a/mkfs.ubifs/hashtable/hashtable.h +++ /dev/null @@ -1,199 +0,0 @@ -/* Copyright (C) 2002 Christopher Clark */ - -#ifndef __HASHTABLE_CWC22_H__ -#define __HASHTABLE_CWC22_H__ - -struct hashtable; - -/* Example of use: - * - * struct hashtable *h; - * struct some_key *k; - * struct some_value *v; - * - * static unsigned int hash_from_key_fn( void *k ); - * static int keys_equal_fn ( void *key1, void *key2 ); - * - * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn); - * k = (struct some_key *) malloc(sizeof(struct some_key)); - * v = (struct some_value *) malloc(sizeof(struct some_value)); - * - * (initialise k and v to suitable values) - * - * if (! hashtable_insert(h,k,v) ) - * { exit(-1); } - * - * if (NULL == (found = hashtable_search(h,k) )) - * { printf("not found!"); } - * - * if (NULL == (found = hashtable_remove(h,k) )) - * { printf("Not found\n"); } - * - */ - -/* Macros may be used to define type-safe(r) hashtable access functions, with - * methods specialized to take known key and value types as parameters. - * - * Example: - * - * Insert this at the start of your file: - * - * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); - * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); - * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); - * - * This defines the functions 'insert_some', 'search_some' and 'remove_some'. - * These operate just like hashtable_insert etc., with the same parameters, - * but their function signatures have 'struct some_key *' rather than - * 'void *', and hence can generate compile time errors if your program is - * supplying incorrect data as a key (and similarly for value). - * - * Note that the hash and key equality functions passed to create_hashtable - * still take 'void *' parameters instead of 'some key *'. This shouldn't be - * a difficult issue as they're only defined and passed once, and the other - * functions will ensure that only valid keys are supplied to them. - * - * The cost for this checking is increased code size and runtime overhead - * - if performance is important, it may be worth switching back to the - * unsafe methods once your program has been debugged with the safe methods. - * This just requires switching to some simple alternative defines - eg: - * #define insert_some hashtable_insert - * - */ - -/***************************************************************************** - * create_hashtable - - * @name create_hashtable - * @param minsize minimum initial size of hashtable - * @param hashfunction function for hashing keys - * @param key_eq_fn function for determining key equality - * @return newly created hashtable or NULL on failure - */ - -struct hashtable * -create_hashtable(unsigned int minsize, - unsigned int (*hashfunction) (void*), - int (*key_eq_fn) (void*,void*)); - -/***************************************************************************** - * hashtable_insert - - * @name hashtable_insert - * @param h the hashtable to insert into - * @param k the key - hashtable claims ownership and will free on removal - * @param v the value - does not claim ownership - * @return non-zero for successful insertion - * - * This function will cause the table to expand if the insertion would take - * the ratio of entries to table size over the maximum load factor. - * - * This function does not check for repeated insertions with a duplicate key. - * The value returned when using a duplicate key is undefined -- when - * the hashtable changes size, the order of retrieval of duplicate key - * entries is reversed. - * If in doubt, remove before insert. - */ - -int -hashtable_insert(struct hashtable *h, void *k, void *v); - -#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ -int fnname (struct hashtable *h, keytype *k, valuetype *v) \ -{ \ - return hashtable_insert(h,k,v); \ -} - -/***************************************************************************** - * hashtable_search - - * @name hashtable_search - * @param h the hashtable to search - * @param k the key to search for - does not claim ownership - * @return the value associated with the key, or NULL if none found - */ - -void * -hashtable_search(struct hashtable *h, void *k); - -#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ -valuetype * fnname (struct hashtable *h, keytype *k) \ -{ \ - return (valuetype *) (hashtable_search(h,k)); \ -} - -/***************************************************************************** - * hashtable_remove - - * @name hashtable_remove - * @param h the hashtable to remove the item from - * @param k the key to search for - does not claim ownership - * @return the value associated with the key, or NULL if none found - */ - -void * /* returns value */ -hashtable_remove(struct hashtable *h, void *k); - -#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ -valuetype * fnname (struct hashtable *h, keytype *k) \ -{ \ - return (valuetype *) (hashtable_remove(h,k)); \ -} - - -/***************************************************************************** - * hashtable_count - - * @name hashtable_count - * @param h the hashtable - * @return the number of items stored in the hashtable - */ -unsigned int -hashtable_count(struct hashtable *h); - - -/***************************************************************************** - * hashtable_destroy - - * @name hashtable_destroy - * @param h the hashtable - * @param free_values whether to call 'free' on the remaining values - */ - -void -hashtable_destroy(struct hashtable *h, int free_values); - -#endif /* __HASHTABLE_CWC22_H__ */ - -/* - * Copyright (c) 2002, Christopher Clark - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * * Neither the name of the original author; nor the names of any contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ diff --git a/mkfs.ubifs/hashtable/hashtable_itr.c b/mkfs.ubifs/hashtable/hashtable_itr.c deleted file mode 100644 index d102453..0000000 --- a/mkfs.ubifs/hashtable/hashtable_itr.c +++ /dev/null @@ -1,176 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#include "hashtable.h" -#include "hashtable_private.h" -#include "hashtable_itr.h" -#include /* defines NULL */ - -/*****************************************************************************/ -/* hashtable_iterator - iterator constructor */ - -struct hashtable_itr * -hashtable_iterator(struct hashtable *h) -{ - unsigned int i, tablelength; - struct hashtable_itr *itr = (struct hashtable_itr *) - malloc(sizeof(struct hashtable_itr)); - if (NULL == itr) return NULL; - itr->h = h; - itr->e = NULL; - itr->parent = NULL; - tablelength = h->tablelength; - itr->index = tablelength; - if (0 == h->entrycount) return itr; - - for (i = 0; i < tablelength; i++) - { - if (NULL != h->table[i]) - { - itr->e = h->table[i]; - itr->index = i; - break; - } - } - return itr; -} - -/*****************************************************************************/ -/* advance - advance the iterator to the next element - * returns zero if advanced to end of table */ - -int -hashtable_iterator_advance(struct hashtable_itr *itr) -{ - unsigned int j,tablelength; - struct entry **table; - struct entry *next; - if (NULL == itr->e) return 0; /* stupidity check */ - - next = itr->e->next; - if (NULL != next) - { - itr->parent = itr->e; - itr->e = next; - return -1; - } - tablelength = itr->h->tablelength; - itr->parent = NULL; - if (tablelength <= (j = ++(itr->index))) - { - itr->e = NULL; - return 0; - } - table = itr->h->table; - while (NULL == (next = table[j])) - { - if (++j >= tablelength) - { - itr->index = tablelength; - itr->e = NULL; - return 0; - } - } - itr->index = j; - itr->e = next; - return -1; -} - -/*****************************************************************************/ -/* remove - remove the entry at the current iterator position - * and advance the iterator, if there is a successive - * element. - * If you want the value, read it before you remove: - * beware memory leaks if you don't. - * Returns zero if end of iteration. */ - -int -hashtable_iterator_remove(struct hashtable_itr *itr) -{ - struct entry *remember_e, *remember_parent; - int ret; - - /* Do the removal */ - if (NULL == (itr->parent)) - { - /* element is head of a chain */ - itr->h->table[itr->index] = itr->e->next; - } else { - /* element is mid-chain */ - itr->parent->next = itr->e->next; - } - /* itr->e is now outside the hashtable */ - remember_e = itr->e; - itr->h->entrycount--; - freekey(remember_e->k); - - /* Advance the iterator, correcting the parent */ - remember_parent = itr->parent; - ret = hashtable_iterator_advance(itr); - if (itr->parent == remember_e) { itr->parent = remember_parent; } - free(remember_e); - return ret; -} - -/*****************************************************************************/ -int /* returns zero if not found */ -hashtable_iterator_search(struct hashtable_itr *itr, - struct hashtable *h, void *k) -{ - struct entry *e, *parent; - unsigned int hashvalue, index; - - hashvalue = hash(h,k); - index = indexFor(h->tablelength,hashvalue); - - e = h->table[index]; - parent = NULL; - while (NULL != e) - { - /* Check hash value to short circuit heavier comparison */ - if ((hashvalue == e->h) && (h->eqfn(k, e->k))) - { - itr->index = index; - itr->e = e; - itr->parent = parent; - itr->h = h; - return -1; - } - parent = e; - e = e->next; - } - return 0; -} - - -/* - * Copyright (c) 2002, 2004, Christopher Clark - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * * Neither the name of the original author; nor the names of any contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ diff --git a/mkfs.ubifs/hashtable/hashtable_itr.h b/mkfs.ubifs/hashtable/hashtable_itr.h deleted file mode 100644 index 5c94a04..0000000 --- a/mkfs.ubifs/hashtable/hashtable_itr.h +++ /dev/null @@ -1,112 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#ifndef __HASHTABLE_ITR_CWC22__ -#define __HASHTABLE_ITR_CWC22__ -#include "hashtable.h" -#include "hashtable_private.h" /* needed to enable inlining */ - -/*****************************************************************************/ -/* This struct is only concrete here to allow the inlining of two of the - * accessor functions. */ -struct hashtable_itr -{ - struct hashtable *h; - struct entry *e; - struct entry *parent; - unsigned int index; -}; - - -/*****************************************************************************/ -/* hashtable_iterator - */ - -struct hashtable_itr * -hashtable_iterator(struct hashtable *h); - -/*****************************************************************************/ -/* hashtable_iterator_key - * - return the value of the (key,value) pair at the current position */ - -static inline void * -hashtable_iterator_key(struct hashtable_itr *i) -{ - return i->e->k; -} - -/*****************************************************************************/ -/* value - return the value of the (key,value) pair at the current position */ - -static inline void * -hashtable_iterator_value(struct hashtable_itr *i) -{ - return i->e->v; -} - -/*****************************************************************************/ -/* advance - advance the iterator to the next element - * returns zero if advanced to end of table */ - -int -hashtable_iterator_advance(struct hashtable_itr *itr); - -/*****************************************************************************/ -/* remove - remove current element and advance the iterator to the next element - * NB: if you need the value to free it, read it before - * removing. ie: beware memory leaks! - * returns zero if advanced to end of table */ - -int -hashtable_iterator_remove(struct hashtable_itr *itr); - -/*****************************************************************************/ -/* search - overwrite the supplied iterator, to point to the entry - * matching the supplied key. - h points to the hashtable to be searched. - * returns zero if not found. */ -int -hashtable_iterator_search(struct hashtable_itr *itr, - struct hashtable *h, void *k); - -#define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \ -int fnname (struct hashtable_itr *i, struct hashtable *h, keytype *k) \ -{ \ - return (hashtable_iterator_search(i,h,k)); \ -} - - - -#endif /* __HASHTABLE_ITR_CWC22__*/ - -/* - * Copyright (c) 2002, 2004, Christopher Clark - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * * Neither the name of the original author; nor the names of any contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ diff --git a/mkfs.ubifs/hashtable/hashtable_private.h b/mkfs.ubifs/hashtable/hashtable_private.h deleted file mode 100644 index 3a558e6..0000000 --- a/mkfs.ubifs/hashtable/hashtable_private.h +++ /dev/null @@ -1,85 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#ifndef __HASHTABLE_PRIVATE_CWC22_H__ -#define __HASHTABLE_PRIVATE_CWC22_H__ - -#include "hashtable.h" - -/*****************************************************************************/ -struct entry -{ - void *k, *v; - unsigned int h; - struct entry *next; -}; - -struct hashtable { - unsigned int tablelength; - struct entry **table; - unsigned int entrycount; - unsigned int loadlimit; - unsigned int primeindex; - unsigned int (*hashfn) (void *k); - int (*eqfn) (void *k1, void *k2); -}; - -/*****************************************************************************/ -unsigned int -hash(struct hashtable *h, void *k); - -/*****************************************************************************/ -/* indexFor */ -static inline unsigned int -indexFor(unsigned int tablelength, unsigned int hashvalue) { - return (hashvalue % tablelength); -}; - -/* Only works if tablelength == 2^N */ -/*static inline unsigned int -indexFor(unsigned int tablelength, unsigned int hashvalue) -{ - return (hashvalue & (tablelength - 1u)); -} -*/ - -/*****************************************************************************/ -#define freekey(X) free(X) -/*define freekey(X) ; */ - - -/*****************************************************************************/ - -#endif /* __HASHTABLE_PRIVATE_CWC22_H__*/ - -/* - * Copyright (c) 2002, Christopher Clark - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * * Neither the name of the original author; nor the names of any contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER - * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -*/ diff --git a/mkfs.ubifs/key.h b/mkfs.ubifs/key.h deleted file mode 100644 index d3a02d4..0000000 --- a/mkfs.ubifs/key.h +++ /dev/null @@ -1,189 +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 header contains various key-related definitions and helper function. - * UBIFS allows several key schemes, so we access key fields only via these - * helpers. At the moment only one key scheme is supported. - * - * Simple key scheme - * ~~~~~~~~~~~~~~~~~ - * - * Keys are 64-bits long. First 32-bits are inode number (parent inode number - * in case of direntry key). Next 3 bits are node type. The last 29 bits are - * 4KiB offset in case of inode node, and direntry hash in case of a direntry - * node. We use "r5" hash borrowed from reiserfs. - */ - -#ifndef __UBIFS_KEY_H__ -#define __UBIFS_KEY_H__ - -/** - * key_mask_hash - mask a valid hash value. - * @val: value to be masked - * - * We use hash values as offset in directories, so values %0 and %1 are - * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This - * function makes sure the reserved values are not used. - */ -static inline uint32_t key_mask_hash(uint32_t hash) -{ - hash &= UBIFS_S_KEY_HASH_MASK; - if (unlikely(hash <= 2)) - hash += 3; - return hash; -} - -/** - * key_r5_hash - R5 hash function (borrowed from reiserfs). - * @s: direntry name - * @len: name length - */ -static inline uint32_t key_r5_hash(const char *s, int len) -{ - uint32_t a = 0; - const signed char *str = (const signed char *)s; - - len = len; - while (*str) { - a += *str << 4; - a += *str >> 4; - a *= 11; - str++; - } - - return key_mask_hash(a); -} - -/** - * key_test_hash - testing hash function. - * @str: direntry name - * @len: name length - */ -static inline uint32_t key_test_hash(const char *str, int len) -{ - uint32_t a = 0; - - len = min_t(uint32_t, len, 4); - memcpy(&a, str, len); - return key_mask_hash(a); -} - -/** - * ino_key_init - initialize inode key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: inode number - */ -static inline void ino_key_init(union ubifs_key *key, ino_t inum) -{ - key->u32[0] = inum; - key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS; -} - -/** - * dent_key_init - initialize directory entry key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: parent inode number - * @nm: direntry name and length - */ -static inline void dent_key_init(const struct ubifs_info *c, - union ubifs_key *key, ino_t inum, - const struct qstr *nm) -{ - uint32_t hash = c->key_hash(nm->name, nm->len); - - ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK)); - key->u32[0] = inum; - key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS); -} - -/** - * data_key_init - initialize data key. - * @c: UBIFS file-system description object - * @key: key to initialize - * @inum: inode number - * @block: block number - */ -static inline void data_key_init(union ubifs_key *key, ino_t inum, - unsigned int block) -{ - ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK)); - key->u32[0] = inum; - key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS); -} - -/** - * key_write - transform a key from in-memory format. - * @c: UBIFS file-system description object - * @from: the key to transform - * @to: the key to store the result - */ -static inline void key_write(const union ubifs_key *from, void *to) -{ - union ubifs_key *t = to; - - t->j32[0] = cpu_to_le32(from->u32[0]); - t->j32[1] = cpu_to_le32(from->u32[1]); - memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8); -} - -/** - * key_write_idx - transform a key from in-memory format for the index. - * @c: UBIFS file-system description object - * @from: the key to transform - * @to: the key to store the result - */ -static inline void key_write_idx(const union ubifs_key *from, void *to) -{ - union ubifs_key *t = to; - - t->j32[0] = cpu_to_le32(from->u32[0]); - t->j32[1] = cpu_to_le32(from->u32[1]); -} - -/** - * keys_cmp - compare keys. - * @c: UBIFS file-system description object - * @key1: the first key to compare - * @key2: the second key to compare - * - * This function compares 2 keys and returns %-1 if @key1 is less than - * @key2, 0 if the keys are equivalent and %1 if @key1 is greater than @key2. - */ -static inline int keys_cmp(const union ubifs_key *key1, - const union ubifs_key *key2) -{ - if (key1->u32[0] < key2->u32[0]) - return -1; - if (key1->u32[0] > key2->u32[0]) - return 1; - if (key1->u32[1] < key2->u32[1]) - return -1; - if (key1->u32[1] > key2->u32[1]) - return 1; - - return 0; -} - -#endif /* !__UBIFS_KEY_H__ */ diff --git a/mkfs.ubifs/lpt.c b/mkfs.ubifs/lpt.c deleted file mode 100644 index 6aa0b88..0000000 --- a/mkfs.ubifs/lpt.c +++ /dev/null @@ -1,578 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2006, 2007 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: Adrian Hunter - * Artem Bityutskiy - */ - -#include "mkfs.ubifs.h" - -/** - * do_calc_lpt_geom - calculate sizes for the LPT area. - * @c: the UBIFS file-system description object - * - * Calculate the sizes of LPT bit fields, nodes, and tree, based on the - * properties of the flash and whether LPT is "big" (c->big_lpt). - */ -static void do_calc_lpt_geom(struct ubifs_info *c) -{ - int n, bits, per_leb_wastage; - long long sz, tot_wastage; - - c->pnode_cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - - n = (c->pnode_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->nnode_cnt = n; - while (n > 1) { - n = (n + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->nnode_cnt += n; - } - - c->lpt_hght = 1; - n = UBIFS_LPT_FANOUT; - while (n < c->pnode_cnt) { - c->lpt_hght += 1; - n <<= UBIFS_LPT_FANOUT_SHIFT; - } - - c->space_bits = fls(c->leb_size) - 3; - c->lpt_lnum_bits = fls(c->lpt_lebs); - c->lpt_offs_bits = fls(c->leb_size - 1); - c->lpt_spc_bits = fls(c->leb_size); - - n = (c->max_leb_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - c->pcnt_bits = fls(n - 1); - - c->lnum_bits = fls(c->max_leb_cnt - 1); - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - (c->big_lpt ? c->pcnt_bits : 0) + - (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT; - c->pnode_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - (c->big_lpt ? c->pcnt_bits : 0) + - (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT; - c->nnode_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - c->lpt_lebs * c->lpt_spc_bits * 2; - c->ltab_sz = (bits + 7) / 8; - - bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + - c->lnum_bits * c->lsave_cnt; - c->lsave_sz = (bits + 7) / 8; - - /* Calculate the minimum LPT size */ - c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz; - c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz; - c->lpt_sz += c->ltab_sz; - c->lpt_sz += c->lsave_sz; - - /* Add wastage */ - sz = c->lpt_sz; - per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz); - sz += per_leb_wastage; - tot_wastage = per_leb_wastage; - while (sz > c->leb_size) { - sz += per_leb_wastage; - sz -= c->leb_size; - tot_wastage += per_leb_wastage; - } - tot_wastage += ALIGN(sz, c->min_io_size) - sz; - c->lpt_sz += tot_wastage; -} - -/** - * calc_dflt_lpt_geom - calculate default LPT geometry. - * @c: the UBIFS file-system description object - * @main_lebs: number of main area LEBs is passed and returned here - * @big_lpt: whether the LPT area is "big" is returned here - * - * The size of the LPT area depends on parameters that themselves are dependent - * on the size of the LPT area. This function, successively recalculates the LPT - * area geometry until the parameters and resultant geometry are consistent. - * - * This function returns %0 on success and a negative error code on failure. - */ -int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt) -{ - int i, lebs_needed; - long long sz; - - /* Start by assuming the minimum number of LPT LEBs */ - c->lpt_lebs = UBIFS_MIN_LPT_LEBS; - c->main_lebs = *main_lebs - c->lpt_lebs; - if (c->main_lebs <= 0) - return -EINVAL; - - /* And assume we will use the small LPT model */ - c->big_lpt = 0; - - /* - * Calculate the geometry based on assumptions above and then see if it - * makes sense - */ - do_calc_lpt_geom(c); - - /* Small LPT model must have lpt_sz < leb_size */ - if (c->lpt_sz > c->leb_size) { - /* Nope, so try again using big LPT model */ - c->big_lpt = 1; - do_calc_lpt_geom(c); - } - - /* Now check there are enough LPT LEBs */ - for (i = 0; i < 64 ; i++) { - sz = c->lpt_sz * 4; /* Allow 4 times the size */ - sz += c->leb_size - 1; - do_div(sz, c->leb_size); - lebs_needed = sz; - if (lebs_needed > c->lpt_lebs) { - /* Not enough LPT LEBs so try again with more */ - c->lpt_lebs = lebs_needed; - c->main_lebs = *main_lebs - c->lpt_lebs; - if (c->main_lebs <= 0) - return -EINVAL; - do_calc_lpt_geom(c); - continue; - } - if (c->ltab_sz > c->leb_size) { - err_msg("LPT ltab too big"); - return -EINVAL; - } - *main_lebs = c->main_lebs; - *big_lpt = c->big_lpt; - return 0; - } - return -EINVAL; -} - -/** - * pack_bits - pack bit fields end-to-end. - * @addr: address at which to pack (passed and next address returned) - * @pos: bit position at which to pack (passed and next position returned) - * @val: value to pack - * @nrbits: number of bits of value to pack (1-32) - */ -static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits) -{ - uint8_t *p = *addr; - int b = *pos; - - if (b) { - *p |= ((uint8_t)val) << b; - nrbits += b; - if (nrbits > 8) { - *++p = (uint8_t)(val >>= (8 - b)); - if (nrbits > 16) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 24) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 32) - *++p = (uint8_t)(val >>= 8); - } - } - } - } else { - *p = (uint8_t)val; - if (nrbits > 8) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 16) { - *++p = (uint8_t)(val >>= 8); - if (nrbits > 24) - *++p = (uint8_t)(val >>= 8); - } - } - } - b = nrbits & 7; - if (b == 0) - p++; - *addr = p; - *pos = b; -} - -/** - * pack_pnode - pack all the bit fields of a pnode. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @pnode: pnode to pack - */ -static void pack_pnode(struct ubifs_info *c, void *buf, - struct ubifs_pnode *pnode) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS); - if (c->big_lpt) - pack_bits(&addr, &pos, pnode->num, c->pcnt_bits); - for (i = 0; i < UBIFS_LPT_FANOUT; i++) { - pack_bits(&addr, &pos, pnode->lprops[i].free >> 3, - c->space_bits); - pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3, - c->space_bits); - if (pnode->lprops[i].flags & LPROPS_INDEX) - pack_bits(&addr, &pos, 1, 1); - else - pack_bits(&addr, &pos, 0, 1); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->pnode_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_nnode - pack all the bit fields of a nnode. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @nnode: nnode to pack - */ -static void pack_nnode(struct ubifs_info *c, void *buf, - struct ubifs_nnode *nnode) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS); - if (c->big_lpt) - pack_bits(&addr, &pos, nnode->num, c->pcnt_bits); - for (i = 0; i < UBIFS_LPT_FANOUT; i++) { - int lnum = nnode->nbranch[i].lnum; - - if (lnum == 0) - lnum = c->lpt_last + 1; - pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits); - pack_bits(&addr, &pos, nnode->nbranch[i].offs, - c->lpt_offs_bits); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->nnode_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_ltab - pack the LPT's own lprops table. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @ltab: LPT's own lprops table to pack - */ -static void pack_ltab(struct ubifs_info *c, void *buf, - struct ubifs_lpt_lprops *ltab) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS); - for (i = 0; i < c->lpt_lebs; i++) { - pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits); - pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits); - } - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->ltab_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * pack_lsave - pack the LPT's save table. - * @c: UBIFS file-system description object - * @buf: buffer into which to pack - * @lsave: LPT's save table to pack - */ -static void pack_lsave(struct ubifs_info *c, void *buf, int *lsave) -{ - uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; - int i, pos = 0; - uint16_t crc; - - pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS); - for (i = 0; i < c->lsave_cnt; i++) - pack_bits(&addr, &pos, lsave[i], c->lnum_bits); - crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, - c->lsave_sz - UBIFS_LPT_CRC_BYTES); - addr = buf; - pos = 0; - pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); -} - -/** - * set_ltab - set LPT LEB properties. - * @c: UBIFS file-system description object - * @lnum: LEB number - * @free: amount of free space - * @dirty: amount of dirty space - */ -static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty) -{ - dbg_msg(3, "LEB %d free %d dirty %d to %d %d", - lnum, c->ltab[lnum - c->lpt_first].free, - c->ltab[lnum - c->lpt_first].dirty, free, dirty); - c->ltab[lnum - c->lpt_first].free = free; - c->ltab[lnum - c->lpt_first].dirty = dirty; -} - -/** - * calc_nnode_num - calculate nnode number. - * @row: the row in the tree (root is zero) - * @col: the column in the row (leftmost is zero) - * - * The nnode number is a number that uniquely identifies a nnode and can be used - * easily to traverse the tree from the root to that nnode. - * - * This function calculates and returns the nnode number for the nnode at @row - * and @col. - */ -static int calc_nnode_num(int row, int col) -{ - int num, bits; - - num = 1; - while (row--) { - bits = (col & (UBIFS_LPT_FANOUT - 1)); - col >>= UBIFS_LPT_FANOUT_SHIFT; - num <<= UBIFS_LPT_FANOUT_SHIFT; - num |= bits; - } - return num; -} - -/** - * create_lpt - create LPT. - * @c: UBIFS file-system description object - * - * This function returns %0 on success and a negative error code on failure. - */ -int create_lpt(struct ubifs_info *c) -{ - int lnum, err = 0, i, j, cnt, len, alen, row; - int blnum, boffs, bsz, bcnt; - struct ubifs_pnode *pnode = NULL; - struct ubifs_nnode *nnode = NULL; - void *buf = NULL, *p; - int *lsave = NULL; - - pnode = malloc(sizeof(struct ubifs_pnode)); - nnode = malloc(sizeof(struct ubifs_nnode)); - buf = malloc(c->leb_size); - lsave = malloc(sizeof(int) * c->lsave_cnt); - if (!pnode || !nnode || !buf || !lsave) { - err = -ENOMEM; - goto out; - } - memset(pnode, 0 , sizeof(struct ubifs_pnode)); - memset(nnode, 0 , sizeof(struct ubifs_nnode)); - - c->lscan_lnum = c->main_first; - - lnum = c->lpt_first; - p = buf; - len = 0; - /* Number of leaf nodes (pnodes) */ - cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) >> UBIFS_LPT_FANOUT_SHIFT; - //printf("pnode_cnt=%d\n",cnt); - - /* - * To calculate the internal node branches, we keep information about - * the level below. - */ - blnum = lnum; /* LEB number of level below */ - boffs = 0; /* Offset of level below */ - bcnt = cnt; /* Number of nodes in level below */ - bsz = c->pnode_sz; /* Size of nodes in level below */ - - /* Add pnodes */ - for (i = 0; i < cnt; i++) { - if (len + c->pnode_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - /* Fill in the pnode */ - for (j = 0; j < UBIFS_LPT_FANOUT; j++) { - int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j; - - if (k < c->main_lebs) - pnode->lprops[j] = c->lpt[k]; - else { - pnode->lprops[j].free = c->leb_size; - pnode->lprops[j].dirty = 0; - pnode->lprops[j].flags = 0; - } - } - pack_pnode(c, p, pnode); - p += c->pnode_sz; - len += c->pnode_sz; - /* - * pnodes are simply numbered left to right starting at zero, - * which means the pnode number can be used easily to traverse - * down the tree to the corresponding pnode. - */ - pnode->num += 1; - } - - row = c->lpt_hght - 1; - /* Add all nnodes, one level at a time */ - while (1) { - /* Number of internal nodes (nnodes) at next level */ - cnt = (cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; - if (cnt == 0) - cnt = 1; - for (i = 0; i < cnt; i++) { - if (len + c->nnode_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, - alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - /* The root is on row zero */ - if (row == 0) { - c->lpt_lnum = lnum; - c->lpt_offs = len; - } - /* Set branches to the level below */ - for (j = 0; j < UBIFS_LPT_FANOUT; j++) { - if (bcnt) { - if (boffs + bsz > c->leb_size) { - blnum += 1; - boffs = 0; - } - nnode->nbranch[j].lnum = blnum; - nnode->nbranch[j].offs = boffs; - boffs += bsz; - bcnt--; - } else { - nnode->nbranch[j].lnum = 0; - nnode->nbranch[j].offs = 0; - } - } - nnode->num = calc_nnode_num(row, i); - pack_nnode(c, p, nnode); - p += c->nnode_sz; - len += c->nnode_sz; - } - /* Row zero is the top row */ - if (row == 0) - break; - /* Update the information about the level below */ - bcnt = cnt; - bsz = c->nnode_sz; - row -= 1; - } - - if (c->big_lpt) { - /* Need to add LPT's save table */ - if (len + c->lsave_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - - c->lsave_lnum = lnum; - c->lsave_offs = len; - - for (i = 0; i < c->lsave_cnt; i++) - lsave[i] = c->main_first + i; - - pack_lsave(c, p, lsave); - p += c->lsave_sz; - len += c->lsave_sz; - } - - /* Need to add LPT's own LEB properties table */ - if (len + c->ltab_sz > c->leb_size) { - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - memset(p, 0xff, alen - len); - err = write_leb(lnum++, alen, buf); - if (err) - goto out; - p = buf; - len = 0; - } - - c->ltab_lnum = lnum; - c->ltab_offs = len; - - /* Update ltab before packing it */ - len += c->ltab_sz; - alen = ALIGN(len, c->min_io_size); - set_ltab(c, lnum, c->leb_size - alen, alen - len); - - pack_ltab(c, p, c->ltab); - p += c->ltab_sz; - - /* Write remaining buffer */ - memset(p, 0xff, alen - len); - err = write_leb(lnum, alen, buf); - if (err) - goto out; - - c->nhead_lnum = lnum; - c->nhead_offs = ALIGN(len, c->min_io_size); - - dbg_msg(1, "lpt_sz: %lld", c->lpt_sz); - dbg_msg(1, "space_bits: %d", c->space_bits); - dbg_msg(1, "lpt_lnum_bits: %d", c->lpt_lnum_bits); - dbg_msg(1, "lpt_offs_bits: %d", c->lpt_offs_bits); - dbg_msg(1, "lpt_spc_bits: %d", c->lpt_spc_bits); - dbg_msg(1, "pcnt_bits: %d", c->pcnt_bits); - dbg_msg(1, "lnum_bits: %d", c->lnum_bits); - dbg_msg(1, "pnode_sz: %d", c->pnode_sz); - dbg_msg(1, "nnode_sz: %d", c->nnode_sz); - dbg_msg(1, "ltab_sz: %d", c->ltab_sz); - dbg_msg(1, "lsave_sz: %d", c->lsave_sz); - dbg_msg(1, "lsave_cnt: %d", c->lsave_cnt); - dbg_msg(1, "lpt_hght: %d", c->lpt_hght); - dbg_msg(1, "big_lpt: %d", c->big_lpt); - dbg_msg(1, "LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs); - dbg_msg(1, "LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs); - dbg_msg(1, "LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs); - if (c->big_lpt) - dbg_msg(1, "LPT lsave is at %d:%d", - c->lsave_lnum, c->lsave_offs); -out: - free(lsave); - free(buf); - free(nnode); - free(pnode); - return err; -} diff --git a/mkfs.ubifs/lpt.h b/mkfs.ubifs/lpt.h deleted file mode 100644 index 4cde59d..0000000 --- a/mkfs.ubifs/lpt.h +++ /dev/null @@ -1,28 +0,0 @@ -/* - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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 - */ - -#ifndef __UBIFS_LPT_H__ -#define __UBIFS_LPT_H__ - -int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt); -int create_lpt(struct ubifs_info *c); - -#endif diff --git a/mkfs.ubifs/mkfs.ubifs.c b/mkfs.ubifs/mkfs.ubifs.c deleted file mode 100644 index ca17e2b..0000000 --- a/mkfs.ubifs/mkfs.ubifs.c +++ /dev/null @@ -1,2324 +0,0 @@ -/* - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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: Adrian Hunter - * Artem Bityutskiy - * Zoltan Sogor - */ - -#define _XOPEN_SOURCE 500 /* For realpath() */ - -#include "mkfs.ubifs.h" -#include -#include "common.h" - -/* Size (prime number) of hash table for link counting */ -#define HASH_TABLE_SIZE 10099 - -/* The node buffer must allow for worst case compression */ -#define NODE_BUFFER_SIZE (UBIFS_DATA_NODE_SZ + \ - UBIFS_BLOCK_SIZE * WORST_COMPR_FACTOR) - -/* Default time granularity in nanoseconds */ -#define DEFAULT_TIME_GRAN 1000000000 - -/** - * struct idx_entry - index entry. - * @next: next index entry (NULL at end of list) - * @prev: previous index entry (NULL at beginning of list) - * @key: key - * @name: directory entry name used for sorting colliding keys by name - * @lnum: LEB number - * @offs: offset - * @len: length - * - * The index is recorded as a linked list which is sorted and used to create - * the bottom level of the on-flash index tree. The remaining levels of the - * index tree are each built from the level below. - */ -struct idx_entry { - struct idx_entry *next; - struct idx_entry *prev; - union ubifs_key key; - char *name; - int lnum; - int offs; - int len; -}; - -/** - * struct inum_mapping - inode number mapping for link counting. - * @next: next inum_mapping (NULL at end of list) - * @prev: previous inum_mapping (NULL at beginning of list) - * @dev: source device on which the source inode number resides - * @inum: source inode number of the file - * @use_inum: target inode number of the file - * @use_nlink: number of links - * @path_name: a path name of the file - * @st: struct stat object containing inode attributes which have to be used - * when the inode is being created (actually only UID, GID, access - * mode, major and minor device numbers) - * - * If a file has more than one hard link, then the number of hard links that - * exist in the source directory hierarchy must be counted to exclude the - * possibility that the file is linked from outside the source directory - * hierarchy. - * - * The inum_mappings are stored in a hash_table of linked lists. - */ -struct inum_mapping { - struct inum_mapping *next; - struct inum_mapping *prev; - dev_t dev; - ino_t inum; - ino_t use_inum; - unsigned int use_nlink; - char *path_name; - struct stat st; -}; - -/* - * Because we copy functions from the kernel, we use a subset of the UBIFS - * file-system description object struct ubifs_info. - */ -struct ubifs_info info_; -static struct ubifs_info *c = &info_; -static libubi_t ubi; - -/* Debug levels are: 0 (none), 1 (statistics), 2 (files) ,3 (more details) */ -int debug_level; -int verbose; -int yes; - -static char *root; -static int root_len; -static struct stat root_st; -static char *output; -static int out_fd; -static int out_ubi; -static int squash_owner; - -/* The 'head' (position) which nodes are written */ -static int head_lnum; -static int head_offs; -static int head_flags; - -/* The index list */ -static struct idx_entry *idx_list_first; -static struct idx_entry *idx_list_last; -static size_t idx_cnt; - -/* Global buffers */ -static void *leb_buf; -static void *node_buf; -static void *block_buf; - -/* Hash table for inode link counting */ -static struct inum_mapping **hash_table; - -/* Inode creation sequence number */ -static unsigned long long creat_sqnum; - -static const char *optstring = "d:r:m:o:D:yh?vVe:c:g:f:Fp:k:x:X:j:R:l:j:UQq"; - -static const struct option longopts[] = { - {"root", 1, NULL, 'r'}, - {"min-io-size", 1, NULL, 'm'}, - {"leb-size", 1, NULL, 'e'}, - {"max-leb-cnt", 1, NULL, 'c'}, - {"output", 1, NULL, 'o'}, - {"devtable", 1, NULL, 'D'}, - {"yes", 0, NULL, 'y'}, - {"help", 0, NULL, 'h'}, - {"verbose", 0, NULL, 'v'}, - {"version", 0, NULL, 'V'}, - {"debug-level", 1, NULL, 'g'}, - {"jrn-size", 1, NULL, 'j'}, - {"reserved", 1, NULL, 'R'}, - {"compr", 1, NULL, 'x'}, - {"favor-percent", 1, NULL, 'X'}, - {"fanout", 1, NULL, 'f'}, - {"space-fixup", 0, NULL, 'F'}, - {"keyhash", 1, NULL, 'k'}, - {"log-lebs", 1, NULL, 'l'}, - {"orph-lebs", 1, NULL, 'p'}, - {"squash-uids" , 0, NULL, 'U'}, - {NULL, 0, NULL, 0} -}; - -static const char *helptext = -"Usage: mkfs.ubifs [OPTIONS] target\n" -"Make a UBIFS file system image from an existing directory tree\n\n" -"Examples:\n" -"Build file system from directory /opt/img, writting the result in the ubifs.img file\n" -"\tmkfs.ubifs -m 512 -e 128KiB -c 100 -r /opt/img ubifs.img\n" -"The same, but writting directly to an UBI volume\n" -"\tmkfs.ubifs -r /opt/img /dev/ubi0_0\n" -"Creating an empty UBIFS filesystem on an UBI volume\n" -"\tmkfs.ubifs /dev/ubi0_0\n\n" -"Options:\n" -"-r, -d, --root=DIR build file system from directory DIR\n" -"-m, --min-io-size=SIZE minimum I/O unit size\n" -"-e, --leb-size=SIZE logical erase block size\n" -"-c, --max-leb-cnt=COUNT maximum logical erase block count\n" -"-o, --output=FILE output to FILE\n" -"-j, --jrn-size=SIZE journal size\n" -"-R, --reserved=SIZE how much space should be reserved for the super-user\n" -"-x, --compr=TYPE compression type - \"lzo\", \"favor_lzo\", \"zlib\" or\n" -" \"none\" (default: \"lzo\")\n" -"-X, --favor-percent may only be used with favor LZO compression and defines\n" -" how many percent better zlib should compress to make\n" -" mkfs.ubifs use zlib instead of LZO (default 20%)\n" -"-f, --fanout=NUM fanout NUM (default: 8)\n" -"-F, --space-fixup file-system free space has to be fixed up on first mount\n" -" (requires kernel version 3.0 or greater)\n" -"-k, --keyhash=TYPE key hash type - \"r5\" or \"test\" (default: \"r5\")\n" -"-p, --orph-lebs=COUNT count of erase blocks for orphans (default: 1)\n" -"-D, --devtable=FILE use device table FILE\n" -"-U, --squash-uids squash owners making all files owned by root\n" -"-l, --log-lebs=COUNT count of erase blocks for the log (used only for\n" -" debugging)\n" -"-y, --yes assume the answer is \"yes\" for all questions\n" -"-v, --verbose verbose operation\n" -"-V, --version display version information\n" -"-g, --debug=LEVEL display debug information (0 - none, 1 - statistics,\n" -" 2 - files, 3 - more details)\n" -"-h, --help display this help text\n\n" -"Note, SIZE is specified in bytes, but it may also be specified in Kilobytes,\n" -"Megabytes, and Gigabytes if a KiB, MiB, or GiB suffix is used.\n\n" -"If you specify \"lzo\" or \"zlib\" compressors, mkfs.ubifs will use this compressor\n" -"for all data. The \"none\" disables any data compression. The \"favor_lzo\" is not\n" -"really a separate compressor. It is just a method of combining \"lzo\" and \"zlib\"\n" -"compressors. Namely, mkfs.ubifs tries to compress data with both \"lzo\" and \"zlib\"\n" -"compressors, then it compares which compressor is better. If \"zlib\" compresses 20\n" -"or more percent better than \"lzo\", mkfs.ubifs chooses \"lzo\", otherwise it chooses\n" -"\"zlib\". The \"--favor-percent\" may specify arbitrary threshold instead of the\n" -"default 20%.\n\n" -"The -F parameter is used to set the \"fix up free space\" flag in the superblock,\n" -"which forces UBIFS to \"fixup\" all the free space which it is going to use. This\n" -"option is useful to work-around the problem of double free space programming: if the\n" -"flasher program which flashes the UBI image is unable to skip NAND pages containing\n" -"only 0xFF bytes, the effect is that some NAND pages are written to twice - first time\n" -"when flashing the image and the second time when UBIFS is mounted and writes useful\n" -"data there. A proper UBI-aware flasher should skip such NAND pages, though. Note, this\n" -"flag may make the first mount very slow, because the \"free space fixup\" procedure\n" -"takes time. This feature is supported by the Linux kernel starting from version 3.0.\n"; - -/** - * make_path - make a path name from a directory and a name. - * @dir: directory path name - * @name: name - */ -static char *make_path(const char *dir, const char *name) -{ - char *s; - - s = malloc(strlen(dir) + strlen(name) + 2); - if (!s) - return NULL; - strcpy(s, dir); - if (dir[strlen(dir) - 1] != '/') - strcat(s, "/"); - strcat(s, name); - return s; -} - -/** - * is_contained - determine if a file is beneath a directory. - * @file: file path name - * @dir: directory path name - * - * This function returns %1 if @file is accessible from the @dir directory and - * %0 otherwise. In case of error, returns %-1. - */ -static int is_contained(const char *file, const char *dir) -{ - char *real_file = NULL; - char *real_dir = NULL; - char *file_base, *copy; - int ret = -1; - - /* Make a copy of the file path because 'dirname()' can modify it */ - copy = strdup(file); - if (!copy) - return -1; - file_base = dirname(copy); - - /* Turn the paths into the canonical form */ - real_file = malloc(PATH_MAX); - if (!real_file) - goto out_free; - - real_dir = malloc(PATH_MAX); - if (!real_dir) - goto out_free; - - if (!realpath(file_base, real_file)) { - perror("Could not canonicalize file path"); - goto out_free; - } - if (!realpath(dir, real_dir)) { - perror("Could not canonicalize directory"); - goto out_free; - } - - ret = !!strstr(real_file, real_dir); - -out_free: - free(copy); - free(real_file); - free(real_dir); - return ret; -} - -/** - * calc_min_log_lebs - calculate the minimum number of log LEBs needed. - * @max_bud_bytes: journal size (buds only) - */ -static int calc_min_log_lebs(unsigned long long max_bud_bytes) -{ - int buds, log_lebs; - unsigned long long log_size; - - buds = (max_bud_bytes + c->leb_size - 1) / c->leb_size; - log_size = ALIGN(UBIFS_REF_NODE_SZ, c->min_io_size); - log_size *= buds; - log_size += ALIGN(UBIFS_CS_NODE_SZ + - UBIFS_REF_NODE_SZ * (c->jhead_cnt + 2), - c->min_io_size); - log_lebs = (log_size + c->leb_size - 1) / c->leb_size; - log_lebs += 1; - return log_lebs; -} - -/** - * add_space_overhead - add UBIFS overhead. - * @size: flash space which should be visible to the user - * - * UBIFS has overhead, and if we need to reserve @size bytes for the user data, - * we have to reserve more flash space, to compensate the overhead. This - * function calculates and returns the amount of physical flash space which - * should be reserved to provide @size bytes for the user. - */ -static long long add_space_overhead(long long size) -{ - int divisor, factor, f, max_idx_node_sz; - - /* - * Do the opposite to what the 'ubifs_reported_space()' kernel UBIFS - * function does. - */ - max_idx_node_sz = ubifs_idx_node_sz(c, c->fanout); - f = c->fanout > 3 ? c->fanout >> 1 : 2; - divisor = UBIFS_BLOCK_SIZE; - factor = UBIFS_MAX_DATA_NODE_SZ; - factor += (max_idx_node_sz * 3) / (f - 1); - size *= factor; - return size / divisor; -} - -static int validate_options(void) -{ - int tmp; - - if (!output) - return err_msg("no output file or UBI volume specified"); - if (root) { - tmp = is_contained(output, root); - if (tmp < 0) - return err_msg("failed to perform output file root check"); - else if (tmp) - return err_msg("output file cannot be in the UBIFS root " - "directory"); - } - if (!is_power_of_2(c->min_io_size)) - return err_msg("min. I/O unit size should be power of 2"); - if (c->leb_size < c->min_io_size) - return err_msg("min. I/O unit cannot be larger than LEB size"); - if (c->leb_size < UBIFS_MIN_LEB_SZ) - return err_msg("too small LEB size %d, minimum is %d", - c->leb_size, UBIFS_MIN_LEB_SZ); - if (c->leb_size % c->min_io_size) - return err_msg("LEB should be multiple of min. I/O units"); - if (c->leb_size % 8) - return err_msg("LEB size has to be multiple of 8"); - if (c->leb_size > UBIFS_MAX_LEB_SZ) - return err_msg("too large LEB size %d, maximum is %d", - c->leb_size, UBIFS_MAX_LEB_SZ); - if (c->max_leb_cnt < UBIFS_MIN_LEB_CNT) - return err_msg("too low max. count of LEBs, minimum is %d", - UBIFS_MIN_LEB_CNT); - if (c->fanout < UBIFS_MIN_FANOUT) - return err_msg("too low fanout, minimum is %d", - UBIFS_MIN_FANOUT); - tmp = c->leb_size - UBIFS_IDX_NODE_SZ; - tmp /= UBIFS_BRANCH_SZ + UBIFS_MAX_KEY_LEN; - if (c->fanout > tmp) - return err_msg("too high fanout, maximum is %d", tmp); - if (c->log_lebs < UBIFS_MIN_LOG_LEBS) - return err_msg("too few log LEBs, minimum is %d", - UBIFS_MIN_LOG_LEBS); - if (c->log_lebs >= c->max_leb_cnt - UBIFS_MIN_LEB_CNT) - return err_msg("too many log LEBs, maximum is %d", - c->max_leb_cnt - UBIFS_MIN_LEB_CNT); - if (c->orph_lebs < UBIFS_MIN_ORPH_LEBS) - return err_msg("too few orphan LEBs, minimum is %d", - UBIFS_MIN_ORPH_LEBS); - if (c->orph_lebs >= c->max_leb_cnt - UBIFS_MIN_LEB_CNT) - return err_msg("too many orphan LEBs, maximum is %d", - c->max_leb_cnt - UBIFS_MIN_LEB_CNT); - tmp = UBIFS_SB_LEBS + UBIFS_MST_LEBS + c->log_lebs + c->lpt_lebs; - tmp += c->orph_lebs + 4; - if (tmp > c->max_leb_cnt) - return err_msg("too low max. count of LEBs, expected at " - "least %d", tmp); - tmp = calc_min_log_lebs(c->max_bud_bytes); - if (c->log_lebs < calc_min_log_lebs(c->max_bud_bytes)) - return err_msg("too few log LEBs, expected at least %d", tmp); - if (c->rp_size >= ((long long)c->leb_size * c->max_leb_cnt) / 2) - return err_msg("too much reserved space %lld", c->rp_size); - return 0; -} - -/** - * get_multiplier - convert size specifier to an integer multiplier. - * @str: the size specifier string - * - * This function parses the @str size specifier, which may be one of - * 'KiB', 'MiB', or 'GiB' into an integer multiplier. Returns positive - * size multiplier in case of success and %-1 in case of failure. - */ -static int get_multiplier(const char *str) -{ - if (!str) - return 1; - - /* Remove spaces before the specifier */ - while (*str == ' ' || *str == '\t') - str += 1; - - if (!strcmp(str, "KiB")) - return 1024; - if (!strcmp(str, "MiB")) - return 1024 * 1024; - if (!strcmp(str, "GiB")) - return 1024 * 1024 * 1024; - - return -1; -} - -/** - * get_bytes - convert a string containing amount of bytes into an - * integer. - * @str: string to convert - * - * This function parses @str which may have one of 'KiB', 'MiB', or 'GiB' size - * specifiers. Returns positive amount of bytes in case of success and %-1 in - * case of failure. - */ -static long long get_bytes(const char *str) -{ - char *endp; - long long bytes = strtoull(str, &endp, 0); - - if (endp == str || bytes < 0) - return err_msg("incorrect amount of bytes: \"%s\"", str); - - if (*endp != '\0') { - int mult = get_multiplier(endp); - - if (mult == -1) - return err_msg("bad size specifier: \"%s\" - " - "should be 'KiB', 'MiB' or 'GiB'", endp); - bytes *= mult; - } - - return bytes; -} -/** - * open_ubi - open the UBI volume. - * @node: name of the UBI volume character device to fetch information about - * - * Returns %0 in case of success and %-1 in case of failure - */ -static int open_ubi(const char *node) -{ - struct stat st; - - if (stat(node, &st) || !S_ISCHR(st.st_mode)) - return -1; - - ubi = libubi_open(); - if (!ubi) - return -1; - if (ubi_get_vol_info(ubi, node, &c->vi)) - return -1; - if (ubi_get_dev_info1(ubi, c->vi.dev_num, &c->di)) - return -1; - return 0; -} - -static int get_options(int argc, char**argv) -{ - int opt, i; - const char *tbl_file = NULL; - struct stat st; - char *endp; - - c->fanout = 8; - c->orph_lebs = 1; - c->key_hash = key_r5_hash; - c->key_len = UBIFS_SK_LEN; - c->default_compr = UBIFS_COMPR_LZO; - c->favor_percent = 20; - c->lsave_cnt = 256; - c->leb_size = -1; - c->min_io_size = -1; - c->max_leb_cnt = -1; - c->max_bud_bytes = -1; - c->log_lebs = -1; - - while (1) { - opt = getopt_long(argc, argv, optstring, longopts, &i); - if (opt == -1) - break; - switch (opt) { - case 'r': - case 'd': - root_len = strlen(optarg); - root = malloc(root_len + 2); - if (!root) - return err_msg("cannot allocate memory"); - - /* - * The further code expects '/' at the end of the root - * UBIFS directory on the host. - */ - memcpy(root, optarg, root_len); - if (root[root_len - 1] != '/') - root[root_len++] = '/'; - root[root_len] = 0; - - /* Make sure the root directory exists */ - if (stat(root, &st)) - return sys_err_msg("bad root directory '%s'", - root); - break; - case 'm': - c->min_io_size = get_bytes(optarg); - if (c->min_io_size <= 0) - return err_msg("bad min. I/O size"); - break; - case 'e': - c->leb_size = get_bytes(optarg); - if (c->leb_size <= 0) - return err_msg("bad LEB size"); - break; - case 'c': - c->max_leb_cnt = get_bytes(optarg); - if (c->max_leb_cnt <= 0) - return err_msg("bad maximum LEB count"); - break; - case 'o': - output = xstrdup(optarg); - break; - case 'D': - tbl_file = optarg; - if (stat(tbl_file, &st) < 0) - return sys_err_msg("bad device table file '%s'", - tbl_file); - break; - case 'y': - yes = 1; - break; - case 'h': - case '?': - printf("%s", helptext); - exit(0); - case 'v': - verbose = 1; - break; - case 'V': - common_print_version(); - exit(0); - case 'g': - debug_level = strtol(optarg, &endp, 0); - if (*endp != '\0' || endp == optarg || - debug_level < 0 || debug_level > 3) - return err_msg("bad debugging level '%s'", - optarg); - break; - case 'f': - c->fanout = strtol(optarg, &endp, 0); - if (*endp != '\0' || endp == optarg || c->fanout <= 0) - return err_msg("bad fanout %s", optarg); - break; - case 'F': - c->space_fixup = 1; - break; - case 'l': - c->log_lebs = strtol(optarg, &endp, 0); - if (*endp != '\0' || endp == optarg || c->log_lebs <= 0) - return err_msg("bad count of log LEBs '%s'", - optarg); - break; - case 'p': - c->orph_lebs = strtol(optarg, &endp, 0); - if (*endp != '\0' || endp == optarg || - c->orph_lebs <= 0) - return err_msg("bad orphan LEB count '%s'", - optarg); - break; - case 'k': - if (strcmp(optarg, "r5") == 0) { - c->key_hash = key_r5_hash; - c->key_hash_type = UBIFS_KEY_HASH_R5; - } else if (strcmp(optarg, "test") == 0) { - c->key_hash = key_test_hash; - c->key_hash_type = UBIFS_KEY_HASH_TEST; - } else - return err_msg("bad key hash"); - break; - case 'x': - if (strcmp(optarg, "favor_lzo") == 0) - c->favor_lzo = 1; - else if (strcmp(optarg, "zlib") == 0) - c->default_compr = UBIFS_COMPR_ZLIB; - else if (strcmp(optarg, "none") == 0) - c->default_compr = UBIFS_COMPR_NONE; - else if (strcmp(optarg, "lzo") != 0) - return err_msg("bad compressor name"); - break; - case 'X': - c->favor_percent = strtol(optarg, &endp, 0); - if (*endp != '\0' || endp == optarg || - c->favor_percent <= 0 || c->favor_percent >= 100) - return err_msg("bad favor LZO percent '%s'", - optarg); - break; - case 'j': - c->max_bud_bytes = get_bytes(optarg); - if (c->max_bud_bytes <= 0) - return err_msg("bad maximum amount of buds"); - break; - case 'R': - c->rp_size = get_bytes(optarg); - if (c->rp_size < 0) - return err_msg("bad reserved bytes count"); - break; - case 'U': - squash_owner = 1; - break; - } - } - - if (optind != argc && !output) - output = xstrdup(argv[optind]); - - if (!output) - return err_msg("not output device or file specified"); - - out_ubi = !open_ubi(output); - - if (out_ubi) { - c->min_io_size = c->di.min_io_size; - c->leb_size = c->vi.leb_size; - if (c->max_leb_cnt == -1) - c->max_leb_cnt = c->vi.rsvd_lebs; - } - - if (c->min_io_size == -1) - return err_msg("min. I/O unit was not specified " - "(use -h for help)"); - - if (c->leb_size == -1) - return err_msg("LEB size was not specified (use -h for help)"); - - if (c->max_leb_cnt == -1) - return err_msg("Maximum count of LEBs was not specified " - "(use -h for help)"); - - if (c->max_bud_bytes == -1) { - int lebs; - - lebs = c->max_leb_cnt - UBIFS_SB_LEBS - UBIFS_MST_LEBS; - lebs -= c->orph_lebs; - if (c->log_lebs != -1) - lebs -= c->log_lebs; - else - lebs -= UBIFS_MIN_LOG_LEBS; - /* - * We do not know lprops geometry so far, so assume minimum - * count of lprops LEBs. - */ - lebs -= UBIFS_MIN_LPT_LEBS; - /* Make the journal about 12.5% of main area lebs */ - c->max_bud_bytes = (lebs / 8) * (long long)c->leb_size; - /* Make the max journal size 8MiB */ - if (c->max_bud_bytes > 8 * 1024 * 1024) - c->max_bud_bytes = 8 * 1024 * 1024; - if (c->max_bud_bytes < 4 * c->leb_size) - c->max_bud_bytes = 4 * c->leb_size; - } - - if (c->log_lebs == -1) { - c->log_lebs = calc_min_log_lebs(c->max_bud_bytes); - c->log_lebs += 2; - } - - if (c->min_io_size < 8) - c->min_io_size = 8; - c->rp_size = add_space_overhead(c->rp_size); - - if (verbose) { - printf("mkfs.ubifs\n"); - printf("\troot: %s\n", root); - printf("\tmin_io_size: %d\n", c->min_io_size); - printf("\tleb_size: %d\n", c->leb_size); - printf("\tmax_leb_cnt: %d\n", c->max_leb_cnt); - printf("\toutput: %s\n", output); - printf("\tjrn_size: %llu\n", c->max_bud_bytes); - printf("\treserved: %llu\n", c->rp_size); - switch (c->default_compr) { - case UBIFS_COMPR_LZO: - printf("\tcompr: lzo\n"); - break; - case UBIFS_COMPR_ZLIB: - printf("\tcompr: zlib\n"); - break; - case UBIFS_COMPR_NONE: - printf("\tcompr: none\n"); - break; - } - printf("\tkeyhash: %s\n", (c->key_hash == key_r5_hash) ? - "r5" : "test"); - printf("\tfanout: %d\n", c->fanout); - printf("\torph_lebs: %d\n", c->orph_lebs); - printf("\tspace_fixup: %d\n", c->space_fixup); - } - - if (validate_options()) - return -1; - - if (tbl_file && parse_devtable(tbl_file)) - return err_msg("cannot parse device table file '%s'", tbl_file); - - return 0; -} - -/** - * prepare_node - fill in the common header. - * @node: node - * @len: node length - */ -static void prepare_node(void *node, int len) -{ - uint32_t crc; - struct ubifs_ch *ch = node; - - ch->magic = cpu_to_le32(UBIFS_NODE_MAGIC); - ch->len = cpu_to_le32(len); - ch->group_type = UBIFS_NO_NODE_GROUP; - ch->sqnum = cpu_to_le64(++c->max_sqnum); - ch->padding[0] = ch->padding[1] = 0; - crc = mtd_crc32(UBIFS_CRC32_INIT, node + 8, len - 8); - ch->crc = cpu_to_le32(crc); -} - -/** - * write_leb - copy the image of a LEB to the output target. - * @lnum: LEB number - * @len: length of data in the buffer - * @buf: buffer (must be at least c->leb_size bytes) - */ -int write_leb(int lnum, int len, void *buf) -{ - off_t pos = (off_t)lnum * c->leb_size; - - dbg_msg(3, "LEB %d len %d", lnum, len); - memset(buf + len, 0xff, c->leb_size - len); - if (out_ubi) - if (ubi_leb_change_start(ubi, out_fd, lnum, c->leb_size)) - return sys_err_msg("ubi_leb_change_start failed"); - - if (lseek(out_fd, pos, SEEK_SET) != pos) - return sys_err_msg("lseek failed seeking %"PRIdoff_t, pos); - - if (write(out_fd, buf, c->leb_size) != c->leb_size) - return sys_err_msg("write failed writing %d bytes at pos %"PRIdoff_t, - c->leb_size, pos); - - return 0; -} - -/** - * write_empty_leb - copy the image of an empty LEB to the output target. - * @lnum: LEB number - */ -static int write_empty_leb(int lnum) -{ - return write_leb(lnum, 0, leb_buf); -} - -/** - * do_pad - pad a buffer to the minimum I/O size. - * @buf: buffer - * @len: buffer length - */ -static int do_pad(void *buf, int len) -{ - int pad_len, alen = ALIGN(len, 8), wlen = ALIGN(alen, c->min_io_size); - uint32_t crc; - - memset(buf + len, 0xff, alen - len); - pad_len = wlen - alen; - dbg_msg(3, "len %d pad_len %d", len, pad_len); - buf += alen; - if (pad_len >= (int)UBIFS_PAD_NODE_SZ) { - struct ubifs_ch *ch = buf; - struct ubifs_pad_node *pad_node = buf; - - ch->magic = cpu_to_le32(UBIFS_NODE_MAGIC); - ch->node_type = UBIFS_PAD_NODE; - ch->group_type = UBIFS_NO_NODE_GROUP; - ch->padding[0] = ch->padding[1] = 0; - ch->sqnum = cpu_to_le64(0); - ch->len = cpu_to_le32(UBIFS_PAD_NODE_SZ); - - pad_len -= UBIFS_PAD_NODE_SZ; - pad_node->pad_len = cpu_to_le32(pad_len); - - crc = mtd_crc32(UBIFS_CRC32_INIT, buf + 8, - UBIFS_PAD_NODE_SZ - 8); - ch->crc = cpu_to_le32(crc); - - memset(buf + UBIFS_PAD_NODE_SZ, 0, pad_len); - } else if (pad_len > 0) - memset(buf, UBIFS_PADDING_BYTE, pad_len); - - return wlen; -} - -/** - * write_node - write a node to a LEB. - * @node: node - * @len: node length - * @lnum: LEB number - */ -static int write_node(void *node, int len, int lnum) -{ - prepare_node(node, len); - - memcpy(leb_buf, node, len); - - len = do_pad(leb_buf, len); - - return write_leb(lnum, len, leb_buf); -} - -/** - * calc_dark - calculate LEB dark space size. - * @c: the UBIFS file-system description object - * @spc: amount of free and dirty space in the LEB - * - * This function calculates amount of dark space in an LEB which has @spc bytes - * of free and dirty space. Returns the calculations result. - * - * Dark space is the space which is not always usable - it depends on which - * nodes are written in which order. E.g., if an LEB has only 512 free bytes, - * it is dark space, because it cannot fit a large data node. So UBIFS cannot - * count on this LEB and treat these 512 bytes as usable because it is not true - * if, for example, only big chunks of uncompressible data will be written to - * the FS. - */ -static int calc_dark(struct ubifs_info *c, int spc) -{ - if (spc < c->dark_wm) - return spc; - - /* - * If we have slightly more space then the dark space watermark, we can - * anyway safely assume it we'll be able to write a node of the - * smallest size there. - */ - if (spc - c->dark_wm < (int)MIN_WRITE_SZ) - return spc - MIN_WRITE_SZ; - - return c->dark_wm; -} - -/** - * set_lprops - set the LEB property values for a LEB. - * @lnum: LEB number - * @offs: end offset of data in the LEB - * @flags: LEB property flags - */ -static void set_lprops(int lnum, int offs, int flags) -{ - int i = lnum - c->main_first, free, dirty; - int a = max_t(int, c->min_io_size, 8); - - free = c->leb_size - ALIGN(offs, a); - dirty = c->leb_size - free - ALIGN(offs, 8); - dbg_msg(3, "LEB %d free %d dirty %d flags %d", lnum, free, dirty, - flags); - if (i < c->main_lebs) { - c->lpt[i].free = free; - c->lpt[i].dirty = dirty; - c->lpt[i].flags = flags; - } - c->lst.total_free += free; - c->lst.total_dirty += dirty; - if (flags & LPROPS_INDEX) - c->lst.idx_lebs += 1; - else { - int spc; - - spc = free + dirty; - if (spc < c->dead_wm) - c->lst.total_dead += spc; - else - c->lst.total_dark += calc_dark(c, spc); - c->lst.total_used += c->leb_size - spc; - } -} - -/** - * add_to_index - add a node key and position to the index. - * @key: node key - * @lnum: node LEB number - * @offs: node offset - * @len: node length - */ -static int add_to_index(union ubifs_key *key, char *name, int lnum, int offs, - int len) -{ - struct idx_entry *e; - - dbg_msg(3, "LEB %d offs %d len %d", lnum, offs, len); - e = malloc(sizeof(struct idx_entry)); - if (!e) - return err_msg("out of memory"); - e->next = NULL; - e->prev = idx_list_last; - e->key = *key; - e->name = name; - e->lnum = lnum; - e->offs = offs; - e->len = len; - if (!idx_list_first) - idx_list_first = e; - if (idx_list_last) - idx_list_last->next = e; - idx_list_last = e; - idx_cnt += 1; - return 0; -} - -/** - * flush_nodes - write the current head and move the head to the next LEB. - */ -static int flush_nodes(void) -{ - int len, err; - - if (!head_offs) - return 0; - len = do_pad(leb_buf, head_offs); - err = write_leb(head_lnum, len, leb_buf); - if (err) - return err; - set_lprops(head_lnum, head_offs, head_flags); - head_lnum += 1; - head_offs = 0; - return 0; -} - -/** - * reserve_space - reserve space for a node on the head. - * @len: node length - * @lnum: LEB number is returned here - * @offs: offset is returned here - */ -static int reserve_space(int len, int *lnum, int *offs) -{ - int err; - - if (len > c->leb_size - head_offs) { - err = flush_nodes(); - if (err) - return err; - } - *lnum = head_lnum; - *offs = head_offs; - head_offs += ALIGN(len, 8); - return 0; -} - -/** - * add_node - write a node to the head. - * @key: node key - * @node: node - * @len: node length - */ -static int add_node(union ubifs_key *key, char *name, void *node, int len) -{ - int err, lnum, offs; - - prepare_node(node, len); - - err = reserve_space(len, &lnum, &offs); - if (err) - return err; - - memcpy(leb_buf + offs, node, len); - memset(leb_buf + offs + len, 0xff, ALIGN(len, 8) - len); - - add_to_index(key, name, lnum, offs, len); - - return 0; -} - -/** - * add_inode_with_data - write an inode. - * @st: stat information of source inode - * @inum: target inode number - * @data: inode data (for special inodes e.g. symlink path etc) - * @data_len: inode data length - * @flags: source inode flags - */ -static int add_inode_with_data(struct stat *st, ino_t inum, void *data, - unsigned int data_len, int flags) -{ - struct ubifs_ino_node *ino = node_buf; - union ubifs_key key; - int len, use_flags = 0; - - if (c->default_compr != UBIFS_COMPR_NONE) - use_flags |= UBIFS_COMPR_FL; - if (flags & FS_COMPR_FL) - use_flags |= UBIFS_COMPR_FL; - if (flags & FS_SYNC_FL) - use_flags |= UBIFS_SYNC_FL; - if (flags & FS_IMMUTABLE_FL) - use_flags |= UBIFS_IMMUTABLE_FL; - if (flags & FS_APPEND_FL) - use_flags |= UBIFS_APPEND_FL; - if (flags & FS_DIRSYNC_FL && S_ISDIR(st->st_mode)) - use_flags |= UBIFS_DIRSYNC_FL; - - memset(ino, 0, UBIFS_INO_NODE_SZ); - - ino_key_init(&key, inum); - ino->ch.node_type = UBIFS_INO_NODE; - key_write(&key, &ino->key); - ino->creat_sqnum = cpu_to_le64(creat_sqnum); - ino->size = cpu_to_le64(st->st_size); - ino->nlink = cpu_to_le32(st->st_nlink); - /* - * The time fields are updated assuming the default time granularity - * of 1 second. To support finer granularities, utime() would be needed. - */ - ino->atime_sec = cpu_to_le64(st->st_atime); - ino->ctime_sec = cpu_to_le64(st->st_ctime); - ino->mtime_sec = cpu_to_le64(st->st_mtime); - ino->atime_nsec = 0; - ino->ctime_nsec = 0; - ino->mtime_nsec = 0; - ino->uid = cpu_to_le32(st->st_uid); - ino->gid = cpu_to_le32(st->st_gid); - ino->mode = cpu_to_le32(st->st_mode); - ino->flags = cpu_to_le32(use_flags); - ino->data_len = cpu_to_le32(data_len); - ino->compr_type = cpu_to_le16(c->default_compr); - if (data_len) - memcpy(&ino->data, data, data_len); - - len = UBIFS_INO_NODE_SZ + data_len; - - return add_node(&key, NULL, ino, len); -} - -/** - * add_inode - write an inode. - * @st: stat information of source inode - * @inum: target inode number - * @flags: source inode flags - */ -static int add_inode(struct stat *st, ino_t inum, int flags) -{ - return add_inode_with_data(st, inum, NULL, 0, flags); -} - -/** - * add_dir_inode - write an inode for a directory. - * @dir: source directory - * @inum: target inode number - * @size: target directory size - * @nlink: target directory link count - * @st: struct stat object describing attributes (except size and nlink) of the - * target inode to create - * - * Note, this function may be called with %NULL @dir, when the directory which - * is being created does not exist at the host file system, but is defined by - * the device table. - */ -static int add_dir_inode(DIR *dir, ino_t inum, loff_t size, unsigned int nlink, - struct stat *st) -{ - int fd, flags = 0; - - st->st_size = size; - st->st_nlink = nlink; - - if (dir) { - fd = dirfd(dir); - if (fd == -1) - return sys_err_msg("dirfd failed"); - if (ioctl(fd, FS_IOC_GETFLAGS, &flags) == -1) - flags = 0; - } - - return add_inode(st, inum, flags); -} - -/** - * add_dev_inode - write an inode for a character or block device. - * @st: stat information of source inode - * @inum: target inode number - * @flags: source inode flags - */ -static int add_dev_inode(struct stat *st, ino_t inum, int flags) -{ - union ubifs_dev_desc dev; - - dev.huge = cpu_to_le64(makedev(major(st->st_rdev), minor(st->st_rdev))); - return add_inode_with_data(st, inum, &dev, 8, flags); -} - -/** - * add_symlink_inode - write an inode for a symbolic link. - * @path_name: path name of symbolic link inode itself (not the link target) - * @st: stat information of source inode - * @inum: target inode number - * @flags: source inode flags - */ -static int add_symlink_inode(const char *path_name, struct stat *st, ino_t inum, - int flags) -{ - char buf[UBIFS_MAX_INO_DATA + 2]; - ssize_t len; - - /* Take the symlink as is */ - len = readlink(path_name, buf, UBIFS_MAX_INO_DATA + 1); - if (len <= 0) - return sys_err_msg("readlink failed for %s", path_name); - if (len > UBIFS_MAX_INO_DATA) - return err_msg("symlink too long for %s", path_name); - - return add_inode_with_data(st, inum, buf, len, flags); -} - -/** - * add_dent_node - write a directory entry node. - * @dir_inum: target inode number of directory - * @name: directory entry name - * @inum: target inode number of the directory entry - * @type: type of the target inode - */ -static int add_dent_node(ino_t dir_inum, const char *name, ino_t inum, - unsigned char type) -{ - struct ubifs_dent_node *dent = node_buf; - union ubifs_key key; - struct qstr dname; - char *kname; - int len; - - dbg_msg(3, "%s ino %lu type %u dir ino %lu", name, (unsigned long)inum, - (unsigned int)type, (unsigned long)dir_inum); - memset(dent, 0, UBIFS_DENT_NODE_SZ); - - dname.name = (void *)name; - dname.len = strlen(name); - - dent->ch.node_type = UBIFS_DENT_NODE; - - dent_key_init(c, &key, dir_inum, &dname); - key_write(&key, dent->key); - dent->inum = cpu_to_le64(inum); - dent->padding1 = 0; - dent->type = type; - dent->nlen = cpu_to_le16(dname.len); - memcpy(dent->name, dname.name, dname.len); - dent->name[dname.len] = '\0'; - - len = UBIFS_DENT_NODE_SZ + dname.len + 1; - - kname = strdup(name); - if (!kname) - return err_msg("cannot allocate memory"); - - return add_node(&key, kname, dent, len); -} - -/** - * lookup_inum_mapping - add an inode mapping for link counting. - * @dev: source device on which source inode number resides - * @inum: source inode number - */ -static struct inum_mapping *lookup_inum_mapping(dev_t dev, ino_t inum) -{ - struct inum_mapping *im; - unsigned int k; - - k = inum % HASH_TABLE_SIZE; - im = hash_table[k]; - while (im) { - if (im->dev == dev && im->inum == inum) - return im; - im = im->next; - } - im = malloc(sizeof(struct inum_mapping)); - if (!im) - return NULL; - im->next = hash_table[k]; - im->prev = NULL; - im->dev = dev; - im->inum = inum; - im->use_inum = 0; - im->use_nlink = 0; - if (hash_table[k]) - hash_table[k]->prev = im; - hash_table[k] = im; - return im; -} - -/** - * all_zero - does a buffer contain only zero bytes. - * @buf: buffer - * @len: buffer length - */ -static int all_zero(void *buf, int len) -{ - unsigned char *p = buf; - - while (len--) - if (*p++ != 0) - return 0; - return 1; -} - -/** - * add_file - write the data of a file and its inode to the output file. - * @path_name: source path name - * @st: source inode stat information - * @inum: target inode number - * @flags: source inode flags - */ -static int add_file(const char *path_name, struct stat *st, ino_t inum, - int flags) -{ - struct ubifs_data_node *dn = node_buf; - void *buf = block_buf; - loff_t file_size = 0; - ssize_t ret, bytes_read; - union ubifs_key key; - int fd, dn_len, err, compr_type, use_compr; - unsigned int block_no = 0; - size_t out_len; - - fd = open(path_name, O_RDONLY | O_LARGEFILE); - if (fd == -1) - return sys_err_msg("failed to open file '%s'", path_name); - do { - /* Read next block */ - bytes_read = 0; - do { - ret = read(fd, buf + bytes_read, - UBIFS_BLOCK_SIZE - bytes_read); - if (ret == -1) { - sys_err_msg("failed to read file '%s'", - path_name); - close(fd); - return 1; - } - bytes_read += ret; - } while (ret != 0 && bytes_read != UBIFS_BLOCK_SIZE); - if (bytes_read == 0) - break; - file_size += bytes_read; - /* Skip holes */ - if (all_zero(buf, bytes_read)) { - block_no += 1; - continue; - } - /* Make data node */ - memset(dn, 0, UBIFS_DATA_NODE_SZ); - data_key_init(&key, inum, block_no++); - dn->ch.node_type = UBIFS_DATA_NODE; - key_write(&key, &dn->key); - dn->size = cpu_to_le32(bytes_read); - out_len = NODE_BUFFER_SIZE - UBIFS_DATA_NODE_SZ; - if (c->default_compr == UBIFS_COMPR_NONE && - (flags & FS_COMPR_FL)) - use_compr = UBIFS_COMPR_LZO; - else - use_compr = c->default_compr; - compr_type = compress_data(buf, bytes_read, &dn->data, - &out_len, use_compr); - dn->compr_type = cpu_to_le16(compr_type); - dn_len = UBIFS_DATA_NODE_SZ + out_len; - /* Add data node to file system */ - err = add_node(&key, NULL, dn, dn_len); - if (err) { - close(fd); - return err; - } - } while (ret != 0); - if (close(fd) == -1) - return sys_err_msg("failed to close file '%s'", path_name); - if (file_size != st->st_size) - return err_msg("file size changed during writing file '%s'", - path_name); - return add_inode(st, inum, flags); -} - -/** - * add_non_dir - write a non-directory to the output file. - * @path_name: source path name - * @inum: target inode number is passed and returned here (due to link counting) - * @nlink: number of links if known otherwise zero - * @type: UBIFS inode type is returned here - * @st: struct stat object containing inode attributes which should be use when - * creating the UBIFS inode - */ -static int add_non_dir(const char *path_name, ino_t *inum, unsigned int nlink, - unsigned char *type, struct stat *st) -{ - int fd, flags = 0; - - dbg_msg(2, "%s", path_name); - - if (S_ISREG(st->st_mode)) { - fd = open(path_name, O_RDONLY); - if (fd == -1) - return sys_err_msg("failed to open file '%s'", - path_name); - if (ioctl(fd, FS_IOC_GETFLAGS, &flags) == -1) - flags = 0; - if (close(fd) == -1) - return sys_err_msg("failed to close file '%s'", - path_name); - *type = UBIFS_ITYPE_REG; - } else if (S_ISCHR(st->st_mode)) - *type = UBIFS_ITYPE_CHR; - else if (S_ISBLK(st->st_mode)) - *type = UBIFS_ITYPE_BLK; - else if (S_ISLNK(st->st_mode)) - *type = UBIFS_ITYPE_LNK; - else if (S_ISSOCK(st->st_mode)) - *type = UBIFS_ITYPE_SOCK; - else if (S_ISFIFO(st->st_mode)) - *type = UBIFS_ITYPE_FIFO; - else - return err_msg("file '%s' has unknown inode type", path_name); - - if (nlink) - st->st_nlink = nlink; - else if (st->st_nlink > 1) { - /* - * If the number of links is greater than 1, then add this file - * later when we know the number of links that we actually have. - * For now, we just put the inode mapping in the hash table. - */ - struct inum_mapping *im; - - im = lookup_inum_mapping(st->st_dev, st->st_ino); - if (!im) - return err_msg("out of memory"); - if (im->use_nlink == 0) { - /* New entry */ - im->use_inum = *inum; - im->use_nlink = 1; - im->path_name = malloc(strlen(path_name) + 1); - if (!im->path_name) - return err_msg("out of memory"); - strcpy(im->path_name, path_name); - } else { - /* Existing entry */ - *inum = im->use_inum; - im->use_nlink += 1; - /* Return unused inode number */ - c->highest_inum -= 1; - } - - memcpy(&im->st, st, sizeof(struct stat)); - return 0; - } else - st->st_nlink = 1; - - creat_sqnum = ++c->max_sqnum; - - if (S_ISREG(st->st_mode)) - return add_file(path_name, st, *inum, flags); - if (S_ISCHR(st->st_mode)) - return add_dev_inode(st, *inum, flags); - if (S_ISBLK(st->st_mode)) - return add_dev_inode(st, *inum, flags); - if (S_ISLNK(st->st_mode)) - return add_symlink_inode(path_name, st, *inum, flags); - if (S_ISSOCK(st->st_mode)) - return add_inode(st, *inum, flags); - if (S_ISFIFO(st->st_mode)) - return add_inode(st, *inum, flags); - - return err_msg("file '%s' has unknown inode type", path_name); -} - -/** - * add_directory - write a directory tree to the output file. - * @dir_name: directory path name - * @dir_inum: UBIFS inode number of directory - * @st: directory inode statistics - * @non_existing: non-zero if this function is called for a directory which - * does not exist on the host file-system and it is being - * created because it is defined in the device table file. - */ -static int add_directory(const char *dir_name, ino_t dir_inum, struct stat *st, - int non_existing) -{ - struct dirent *entry; - DIR *dir = NULL; - int err = 0; - loff_t size = UBIFS_INO_NODE_SZ; - char *name = NULL; - unsigned int nlink = 2; - struct path_htbl_element *ph_elt; - struct name_htbl_element *nh_elt = NULL; - struct hashtable_itr *itr; - ino_t inum; - unsigned char type; - unsigned long long dir_creat_sqnum = ++c->max_sqnum; - - dbg_msg(2, "%s", dir_name); - if (!non_existing) { - dir = opendir(dir_name); - if (dir == NULL) - return sys_err_msg("cannot open directory '%s'", - dir_name); - } - - /* - * Check whether this directory contains files which should be - * added/changed because they were specified in the device table. - * @ph_elt will be non-zero if yes. - */ - ph_elt = devtbl_find_path(dir_name + root_len - 1); - - /* - * Before adding the directory itself, we have to iterate over all the - * entries the device table adds to this directory and create them. - */ - for (; !non_existing;) { - struct stat dent_st; - - errno = 0; - entry = readdir(dir); - if (!entry) { - if (errno == 0) - break; - sys_err_msg("error reading directory '%s'", dir_name); - err = -1; - break; - } - - if (strcmp(".", entry->d_name) == 0) - continue; - if (strcmp("..", entry->d_name) == 0) - continue; - - if (ph_elt) - /* - * This directory was referred to at the device table - * file. Check if this directory entry is referred at - * too. - */ - nh_elt = devtbl_find_name(ph_elt, entry->d_name); - - /* - * We are going to create the file corresponding to this - * directory entry (@entry->d_name). We use 'struct stat' - * object to pass information about file attributes (actually - * only about UID, GID, mode, major, and minor). Get attributes - * for this file from the UBIFS rootfs on the host. - */ - free(name); - name = make_path(dir_name, entry->d_name); - if (lstat(name, &dent_st) == -1) { - sys_err_msg("lstat failed for file '%s'", name); - goto out_free; - } - - if (squash_owner) - /* - * Squash UID/GID. But the device table may override - * this. - */ - dent_st.st_uid = dent_st.st_gid = 0; - - /* - * And if the device table describes the same file, override - * the attributes. However, this is not allowed for device node - * files. - */ - if (nh_elt && override_attributes(&dent_st, ph_elt, nh_elt)) - goto out_free; - - inum = ++c->highest_inum; - - if (S_ISDIR(dent_st.st_mode)) { - err = add_directory(name, inum, &dent_st, 0); - if (err) - goto out_free; - nlink += 1; - type = UBIFS_ITYPE_DIR; - } else { - err = add_non_dir(name, &inum, 0, &type, &dent_st); - if (err) - goto out_free; - } - - err = add_dent_node(dir_inum, entry->d_name, inum, type); - if (err) - goto out_free; - size += ALIGN(UBIFS_DENT_NODE_SZ + strlen(entry->d_name) + 1, - 8); - } - - /* - * OK, we have created all files in this directory (recursively), let's - * also create all files described in the device table. All t - */ - nh_elt = first_name_htbl_element(ph_elt, &itr); - while (nh_elt) { - struct stat fake_st; - - /* - * We prohibit creating regular files using the device table, - * the device table may only re-define attributes of regular - * files. - */ - if (S_ISREG(nh_elt->mode)) { - err_msg("Bad device table entry %s/%s - it is " - "prohibited to create regular files " - "via device table", - strcmp(ph_elt->path, "/") ? ph_elt->path : "", - nh_elt->name); - goto out_free; - } - - memcpy(&fake_st, &root_st, sizeof(struct stat)); - fake_st.st_uid = nh_elt->uid; - fake_st.st_uid = nh_elt->uid; - fake_st.st_mode = nh_elt->mode; - fake_st.st_rdev = nh_elt->dev; - fake_st.st_nlink = 1; - - free(name); - name = make_path(dir_name, nh_elt->name); - inum = ++c->highest_inum; - - if (S_ISDIR(nh_elt->mode)) { - err = add_directory(name, inum, &fake_st, 1); - if (err) - goto out_free; - nlink += 1; - type = UBIFS_ITYPE_DIR; - } else { - err = add_non_dir(name, &inum, 0, &type, &fake_st); - if (err) - goto out_free; - } - - err = add_dent_node(dir_inum, nh_elt->name, inum, type); - if (err) - goto out_free; - size += ALIGN(UBIFS_DENT_NODE_SZ + strlen(nh_elt->name) + 1, 8); - - nh_elt = next_name_htbl_element(ph_elt, &itr); - } - - creat_sqnum = dir_creat_sqnum; - - err = add_dir_inode(dir, dir_inum, size, nlink, st); - if (err) - goto out_free; - - free(name); - if (!non_existing && closedir(dir) == -1) - return sys_err_msg("error closing directory '%s'", dir_name); - - return 0; - -out_free: - free(name); - if (!non_existing) - closedir(dir); - return -1; -} - -/** - * add_multi_linked_files - write all the files for which we counted links. - */ -static int add_multi_linked_files(void) -{ - int i, err; - - for (i = 0; i < HASH_TABLE_SIZE; i++) { - struct inum_mapping *im; - unsigned char type = 0; - - for (im = hash_table[i]; im; im = im->next) { - dbg_msg(2, "%s", im->path_name); - err = add_non_dir(im->path_name, &im->use_inum, - im->use_nlink, &type, &im->st); - if (err) - return err; - } - } - return 0; -} - -/** - * write_data - write the files and directories. - */ -static int write_data(void) -{ - int err; - mode_t mode = S_IFDIR | S_IRWXU | S_IRGRP | S_IXGRP | S_IROTH | S_IXOTH; - - if (root) { - err = stat(root, &root_st); - if (err) - return sys_err_msg("bad root file-system directory '%s'", - root); - } else { - root_st.st_mtime = time(NULL); - root_st.st_atime = root_st.st_ctime = root_st.st_mtime; - root_st.st_mode = mode; - } - - head_flags = 0; - err = add_directory(root, UBIFS_ROOT_INO, &root_st, !root); - if (err) - return err; - err = add_multi_linked_files(); - if (err) - return err; - return flush_nodes(); -} - -static int namecmp(const char *name1, const char *name2) -{ - size_t len1 = strlen(name1), len2 = strlen(name2); - size_t clen = (len1 < len2) ? len1 : len2; - int cmp; - - cmp = memcmp(name1, name2, clen); - if (cmp) - return cmp; - return (len1 < len2) ? -1 : 1; -} - -static int cmp_idx(const void *a, const void *b) -{ - const struct idx_entry *e1 = *(const struct idx_entry **)a; - const struct idx_entry *e2 = *(const struct idx_entry **)b; - int cmp; - - cmp = keys_cmp(&e1->key, &e2->key); - if (cmp) - return cmp; - return namecmp(e1->name, e2->name); -} - -/** - * add_idx_node - write an index node to the head. - * @node: index node - * @child_cnt: number of children of this index node - */ -static int add_idx_node(void *node, int child_cnt) -{ - int err, lnum, offs, len; - - len = ubifs_idx_node_sz(c, child_cnt); - - prepare_node(node, len); - - err = reserve_space(len, &lnum, &offs); - if (err) - return err; - - memcpy(leb_buf + offs, node, len); - memset(leb_buf + offs + len, 0xff, ALIGN(len, 8) - len); - - c->old_idx_sz += ALIGN(len, 8); - - dbg_msg(3, "at %d:%d len %d index size %llu", lnum, offs, len, - c->old_idx_sz); - - /* The last index node written will be the root */ - c->zroot.lnum = lnum; - c->zroot.offs = offs; - c->zroot.len = len; - - return 0; -} - -/** - * write_index - write out the index. - */ -static int write_index(void) -{ - size_t sz, i, cnt, idx_sz, pstep, bcnt; - struct idx_entry **idx_ptr, **p; - struct ubifs_idx_node *idx; - struct ubifs_branch *br; - int child_cnt = 0, j, level, blnum, boffs, blen, blast_len, err; - - dbg_msg(1, "leaf node count: %zd", idx_cnt); - - /* Reset the head for the index */ - head_flags = LPROPS_INDEX; - /* Allocate index node */ - idx_sz = ubifs_idx_node_sz(c, c->fanout); - idx = malloc(idx_sz); - if (!idx) - return err_msg("out of memory"); - /* Make an array of pointers to sort the index list */ - sz = idx_cnt * sizeof(struct idx_entry *); - if (sz / sizeof(struct idx_entry *) != idx_cnt) { - free(idx); - return err_msg("index is too big (%zu entries)", idx_cnt); - } - idx_ptr = malloc(sz); - if (!idx_ptr) { - free(idx); - return err_msg("out of memory - needed %zu bytes for index", - sz); - } - idx_ptr[0] = idx_list_first; - for (i = 1; i < idx_cnt; i++) - idx_ptr[i] = idx_ptr[i - 1]->next; - qsort(idx_ptr, idx_cnt, sizeof(struct idx_entry *), cmp_idx); - /* Write level 0 index nodes */ - cnt = idx_cnt / c->fanout; - if (idx_cnt % c->fanout) - cnt += 1; - p = idx_ptr; - blnum = head_lnum; - boffs = head_offs; - for (i = 0; i < cnt; i++) { - /* - * Calculate the child count. All index nodes are created full - * except for the last index node on each row. - */ - if (i == cnt - 1) { - child_cnt = idx_cnt % c->fanout; - if (child_cnt == 0) - child_cnt = c->fanout; - } else - child_cnt = c->fanout; - memset(idx, 0, idx_sz); - idx->ch.node_type = UBIFS_IDX_NODE; - idx->child_cnt = cpu_to_le16(child_cnt); - idx->level = cpu_to_le16(0); - for (j = 0; j < child_cnt; j++, p++) { - br = ubifs_idx_branch(c, idx, j); - key_write_idx(&(*p)->key, &br->key); - br->lnum = cpu_to_le32((*p)->lnum); - br->offs = cpu_to_le32((*p)->offs); - br->len = cpu_to_le32((*p)->len); - } - add_idx_node(idx, child_cnt); - } - /* Write level 1 index nodes and above */ - level = 0; - pstep = 1; - while (cnt > 1) { - /* - * 'blast_len' is the length of the last index node in the level - * below. - */ - blast_len = ubifs_idx_node_sz(c, child_cnt); - /* 'bcnt' is the number of index nodes in the level below */ - bcnt = cnt; - /* 'cnt' is the number of index nodes in this level */ - cnt = (cnt + c->fanout - 1) / c->fanout; - if (cnt == 0) - cnt = 1; - level += 1; - /* - * The key of an index node is the same as the key of its first - * child. Thus we can get the key by stepping along the bottom - * level 'p' with an increasing large step 'pstep'. - */ - p = idx_ptr; - pstep *= c->fanout; - for (i = 0; i < cnt; i++) { - /* - * Calculate the child count. All index nodes are - * created full except for the last index node on each - * row. - */ - if (i == cnt - 1) { - child_cnt = bcnt % c->fanout; - if (child_cnt == 0) - child_cnt = c->fanout; - } else - child_cnt = c->fanout; - memset(idx, 0, idx_sz); - idx->ch.node_type = UBIFS_IDX_NODE; - idx->child_cnt = cpu_to_le16(child_cnt); - idx->level = cpu_to_le16(level); - for (j = 0; j < child_cnt; j++) { - size_t bn = i * c->fanout + j; - - /* - * The length of the index node in the level - * below is 'idx_sz' except when it is the last - * node on the row. i.e. all the others on the - * row are full. - */ - if (bn == bcnt - 1) - blen = blast_len; - else - blen = idx_sz; - /* - * 'blnum' and 'boffs' hold the position of the - * index node on the level below. - */ - if (boffs + blen > c->leb_size) { - blnum += 1; - boffs = 0; - } - /* - * Fill in the branch with the key and position - * of the index node from the level below. - */ - br = ubifs_idx_branch(c, idx, j); - key_write_idx(&(*p)->key, &br->key); - br->lnum = cpu_to_le32(blnum); - br->offs = cpu_to_le32(boffs); - br->len = cpu_to_le32(blen); - /* - * Step to the next index node on the level - * below. - */ - boffs += ALIGN(blen, 8); - p += pstep; - } - add_idx_node(idx, child_cnt); - } - } - - /* Free stuff */ - for (i = 0; i < idx_cnt; i++) - free(idx_ptr[i]); - free(idx_ptr); - free(idx); - - dbg_msg(1, "zroot is at %d:%d len %d", c->zroot.lnum, c->zroot.offs, - c->zroot.len); - - /* Set the index head */ - c->ihead_lnum = head_lnum; - c->ihead_offs = ALIGN(head_offs, c->min_io_size); - dbg_msg(1, "ihead is at %d:%d", c->ihead_lnum, c->ihead_offs); - - /* Flush the last index LEB */ - err = flush_nodes(); - if (err) - return err; - - return 0; -} - -/** - * set_gc_lnum - set the LEB number reserved for the garbage collector. - */ -static int set_gc_lnum(void) -{ - int err; - - c->gc_lnum = head_lnum++; - err = write_empty_leb(c->gc_lnum); - if (err) - return err; - set_lprops(c->gc_lnum, 0, 0); - c->lst.empty_lebs += 1; - return 0; -} - -/** - * finalize_leb_cnt - now that we know how many LEBs we used. - */ -static int finalize_leb_cnt(void) -{ - c->leb_cnt = head_lnum; - if (c->leb_cnt > c->max_leb_cnt) - return err_msg("max_leb_cnt too low (%d needed)", c->leb_cnt); - c->main_lebs = c->leb_cnt - c->main_first; - if (verbose) { - printf("\tsuper lebs: %d\n", UBIFS_SB_LEBS); - printf("\tmaster lebs: %d\n", UBIFS_MST_LEBS); - printf("\tlog_lebs: %d\n", c->log_lebs); - printf("\tlpt_lebs: %d\n", c->lpt_lebs); - printf("\torph_lebs: %d\n", c->orph_lebs); - printf("\tmain_lebs: %d\n", c->main_lebs); - printf("\tgc lebs: %d\n", 1); - printf("\tindex lebs: %d\n", c->lst.idx_lebs); - printf("\tleb_cnt: %d\n", c->leb_cnt); - } - dbg_msg(1, "total_free: %llu", c->lst.total_free); - dbg_msg(1, "total_dirty: %llu", c->lst.total_dirty); - dbg_msg(1, "total_used: %llu", c->lst.total_used); - dbg_msg(1, "total_dead: %llu", c->lst.total_dead); - dbg_msg(1, "total_dark: %llu", c->lst.total_dark); - dbg_msg(1, "index size: %llu", c->old_idx_sz); - dbg_msg(1, "empty_lebs: %d", c->lst.empty_lebs); - return 0; -} - -/** - * write_super - write the super block. - */ -static int write_super(void) -{ - struct ubifs_sb_node sup; - - memset(&sup, 0, UBIFS_SB_NODE_SZ); - - sup.ch.node_type = UBIFS_SB_NODE; - sup.key_hash = c->key_hash_type; - sup.min_io_size = cpu_to_le32(c->min_io_size); - sup.leb_size = cpu_to_le32(c->leb_size); - sup.leb_cnt = cpu_to_le32(c->leb_cnt); - sup.max_leb_cnt = cpu_to_le32(c->max_leb_cnt); - sup.max_bud_bytes = cpu_to_le64(c->max_bud_bytes); - sup.log_lebs = cpu_to_le32(c->log_lebs); - sup.lpt_lebs = cpu_to_le32(c->lpt_lebs); - sup.orph_lebs = cpu_to_le32(c->orph_lebs); - sup.jhead_cnt = cpu_to_le32(c->jhead_cnt); - sup.fanout = cpu_to_le32(c->fanout); - sup.lsave_cnt = cpu_to_le32(c->lsave_cnt); - sup.fmt_version = cpu_to_le32(UBIFS_FORMAT_VERSION); - sup.default_compr = cpu_to_le16(c->default_compr); - sup.rp_size = cpu_to_le64(c->rp_size); - sup.time_gran = cpu_to_le32(DEFAULT_TIME_GRAN); - uuid_generate_random(sup.uuid); - if (verbose) { - char s[40]; - - uuid_unparse_upper(sup.uuid, s); - printf("\tUUID: %s\n", s); - } - if (c->big_lpt) - sup.flags |= cpu_to_le32(UBIFS_FLG_BIGLPT); - if (c->space_fixup) - sup.flags |= cpu_to_le32(UBIFS_FLG_SPACE_FIXUP); - - return write_node(&sup, UBIFS_SB_NODE_SZ, UBIFS_SB_LNUM); -} - -/** - * write_master - write the master node. - */ -static int write_master(void) -{ - struct ubifs_mst_node mst; - int err; - - memset(&mst, 0, UBIFS_MST_NODE_SZ); - - mst.ch.node_type = UBIFS_MST_NODE; - mst.log_lnum = cpu_to_le32(UBIFS_LOG_LNUM); - mst.highest_inum = cpu_to_le64(c->highest_inum); - mst.cmt_no = cpu_to_le64(0); - mst.flags = cpu_to_le32(UBIFS_MST_NO_ORPHS); - mst.root_lnum = cpu_to_le32(c->zroot.lnum); - mst.root_offs = cpu_to_le32(c->zroot.offs); - mst.root_len = cpu_to_le32(c->zroot.len); - mst.gc_lnum = cpu_to_le32(c->gc_lnum); - mst.ihead_lnum = cpu_to_le32(c->ihead_lnum); - mst.ihead_offs = cpu_to_le32(c->ihead_offs); - mst.index_size = cpu_to_le64(c->old_idx_sz); - mst.lpt_lnum = cpu_to_le32(c->lpt_lnum); - mst.lpt_offs = cpu_to_le32(c->lpt_offs); - mst.nhead_lnum = cpu_to_le32(c->nhead_lnum); - mst.nhead_offs = cpu_to_le32(c->nhead_offs); - mst.ltab_lnum = cpu_to_le32(c->ltab_lnum); - mst.ltab_offs = cpu_to_le32(c->ltab_offs); - mst.lsave_lnum = cpu_to_le32(c->lsave_lnum); - mst.lsave_offs = cpu_to_le32(c->lsave_offs); - mst.lscan_lnum = cpu_to_le32(c->lscan_lnum); - mst.empty_lebs = cpu_to_le32(c->lst.empty_lebs); - mst.idx_lebs = cpu_to_le32(c->lst.idx_lebs); - mst.total_free = cpu_to_le64(c->lst.total_free); - mst.total_dirty = cpu_to_le64(c->lst.total_dirty); - mst.total_used = cpu_to_le64(c->lst.total_used); - mst.total_dead = cpu_to_le64(c->lst.total_dead); - mst.total_dark = cpu_to_le64(c->lst.total_dark); - mst.leb_cnt = cpu_to_le32(c->leb_cnt); - - err = write_node(&mst, UBIFS_MST_NODE_SZ, UBIFS_MST_LNUM); - if (err) - return err; - - err = write_node(&mst, UBIFS_MST_NODE_SZ, UBIFS_MST_LNUM + 1); - if (err) - return err; - - return 0; -} - -/** - * write_log - write an empty log. - */ -static int write_log(void) -{ - struct ubifs_cs_node cs; - int err, i, lnum; - - lnum = UBIFS_LOG_LNUM; - - cs.ch.node_type = UBIFS_CS_NODE; - cs.cmt_no = cpu_to_le64(0); - - err = write_node(&cs, UBIFS_CS_NODE_SZ, lnum); - if (err) - return err; - - lnum += 1; - - for (i = 1; i < c->log_lebs; i++, lnum++) { - err = write_empty_leb(lnum); - if (err) - return err; - } - - return 0; -} - -/** - * write_lpt - write the LEB properties tree. - */ -static int write_lpt(void) -{ - int err, lnum; - - err = create_lpt(c); - if (err) - return err; - - lnum = c->nhead_lnum + 1; - while (lnum <= c->lpt_last) { - err = write_empty_leb(lnum++); - if (err) - return err; - } - - return 0; -} - -/** - * write_orphan_area - write an empty orphan area. - */ -static int write_orphan_area(void) -{ - int err, i, lnum; - - lnum = UBIFS_LOG_LNUM + c->log_lebs + c->lpt_lebs; - for (i = 0; i < c->orph_lebs; i++, lnum++) { - err = write_empty_leb(lnum); - if (err) - return err; - } - return 0; -} - -/** - * check_volume_empty - check if the UBI volume is empty. - * - * This function checks if the UBI volume is empty by looking if its LEBs are - * mapped or not. - * - * Returns %0 in case of success, %1 is the volume is not empty, - * and a negative error code in case of failure. - */ -static int check_volume_empty(void) -{ - int lnum, err; - - for (lnum = 0; lnum < c->vi.rsvd_lebs; lnum++) { - err = ubi_is_mapped(out_fd, lnum); - if (err < 0) - return err; - if (err == 1) - return 1; - } - return 0; -} - -/** - * open_target - open the output target. - * - * Open the output target. The target can be an UBI volume - * or a file. - * - * Returns %0 in case of success and %-1 in case of failure. - */ -static int open_target(void) -{ - if (out_ubi) { - out_fd = open(output, O_RDWR | O_EXCL); - - if (out_fd == -1) - return sys_err_msg("cannot open the UBI volume '%s'", - output); - if (ubi_set_property(out_fd, UBI_VOL_PROP_DIRECT_WRITE, 1)) - return sys_err_msg("ubi_set_property failed"); - - if (!yes && check_volume_empty()) { - if (!prompt("UBI volume is not empty. Format anyways?", false)) - return err_msg("UBI volume is not empty"); - } - } else { - out_fd = open(output, O_CREAT | O_RDWR | O_TRUNC, - S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH); - if (out_fd == -1) - return sys_err_msg("cannot create output file '%s'", - output); - } - return 0; -} - - -/** - * close_target - close the output target. - * - * Close the output target. If the target was an UBI - * volume, also close libubi. - * - * Returns %0 in case of success and %-1 in case of failure. - */ -static int close_target(void) -{ - if (ubi) - libubi_close(ubi); - if (out_fd >= 0 && close(out_fd) == -1) - return sys_err_msg("cannot close the target '%s'", output); - if (output) - free(output); - return 0; -} - -/** - * init - initialize things. - */ -static int init(void) -{ - int err, i, main_lebs, big_lpt = 0, sz; - - c->highest_inum = UBIFS_FIRST_INO; - - c->jhead_cnt = 1; - - main_lebs = c->max_leb_cnt - UBIFS_SB_LEBS - UBIFS_MST_LEBS; - main_lebs -= c->log_lebs + c->orph_lebs; - - err = calc_dflt_lpt_geom(c, &main_lebs, &big_lpt); - if (err) - return err; - - c->main_first = UBIFS_LOG_LNUM + c->log_lebs + c->lpt_lebs + - c->orph_lebs; - head_lnum = c->main_first; - head_offs = 0; - - c->lpt_first = UBIFS_LOG_LNUM + c->log_lebs; - c->lpt_last = c->lpt_first + c->lpt_lebs - 1; - - c->lpt = malloc(c->main_lebs * sizeof(struct ubifs_lprops)); - if (!c->lpt) - return err_msg("unable to allocate LPT"); - - c->ltab = malloc(c->lpt_lebs * sizeof(struct ubifs_lprops)); - if (!c->ltab) - return err_msg("unable to allocate LPT ltab"); - - /* Initialize LPT's own lprops */ - for (i = 0; i < c->lpt_lebs; i++) { - c->ltab[i].free = c->leb_size; - c->ltab[i].dirty = 0; - } - - c->dead_wm = ALIGN(MIN_WRITE_SZ, c->min_io_size); - c->dark_wm = ALIGN(UBIFS_MAX_NODE_SZ, c->min_io_size); - dbg_msg(1, "dead_wm %d dark_wm %d", c->dead_wm, c->dark_wm); - - leb_buf = malloc(c->leb_size); - if (!leb_buf) - return err_msg("out of memory"); - - node_buf = malloc(NODE_BUFFER_SIZE); - if (!node_buf) - return err_msg("out of memory"); - - block_buf = malloc(UBIFS_BLOCK_SIZE); - if (!block_buf) - return err_msg("out of memory"); - - sz = sizeof(struct inum_mapping *) * HASH_TABLE_SIZE; - hash_table = malloc(sz); - if (!hash_table) - return err_msg("out of memory"); - memset(hash_table, 0, sz); - - err = init_compression(); - if (err) - return err; - - return 0; -} - -static void destroy_hash_table(void) -{ - int i; - - for (i = 0; i < HASH_TABLE_SIZE; i++) { - struct inum_mapping *im, *q; - - for (im = hash_table[i]; im; ) { - q = im; - im = im->next; - free(q->path_name); - free(q); - } - } -} - -/** - * deinit - deinitialize things. - */ -static void deinit(void) -{ - free(c->lpt); - free(c->ltab); - free(leb_buf); - free(node_buf); - free(block_buf); - destroy_hash_table(); - free(hash_table); - destroy_compression(); - free_devtable_info(); -} - -/** - * mkfs - make the file system. - * - * Each on-flash area has a corresponding function to create it. The order of - * the functions reflects what information must be known to complete each stage. - * As a consequence the output file is not written sequentially. No effort has - * been made to make efficient use of memory or to allow for the possibility of - * incremental updates to the output file. - */ -static int mkfs(void) -{ - int err = 0; - - err = init(); - if (err) - goto out; - - err = write_data(); - if (err) - goto out; - - err = set_gc_lnum(); - if (err) - goto out; - - err = write_index(); - if (err) - goto out; - - err = finalize_leb_cnt(); - if (err) - goto out; - - err = write_lpt(); - if (err) - goto out; - - err = write_super(); - if (err) - goto out; - - err = write_master(); - if (err) - goto out; - - err = write_log(); - if (err) - goto out; - - err = write_orphan_area(); - -out: - deinit(); - return err; -} - -int main(int argc, char *argv[]) -{ - int err; - - err = get_options(argc, argv); - if (err) - return err; - - err = open_target(); - if (err) - return err; - - err = mkfs(); - if (err) { - close_target(); - return err; - } - - err = close_target(); - if (err) - return err; - - if (verbose) - printf("Success!\n"); - - return 0; -} diff --git a/mkfs.ubifs/mkfs.ubifs.h b/mkfs.ubifs/mkfs.ubifs.h deleted file mode 100644 index 944a159..0000000 --- a/mkfs.ubifs/mkfs.ubifs.h +++ /dev/null @@ -1,150 +0,0 @@ -/* - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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 - * Zoltan Sogor - */ - -#ifndef __MKFS_UBIFS_H__ -#define __MKFS_UBIFS_H__ - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include - -/* common.h requires the PROGRAM_NAME macro */ -#define PROGRAM_NAME "mkfs.ubifs" -#include "common.h" - -#include "libubi.h" -#include "defs.h" -#include "crc16.h" -#include "ubifs.h" -#include "key.h" -#include "lpt.h" -#include "compr.h" - -/* - * Compression flags are duplicated so that compr.c can compile without ubifs.h. - * Here we make sure they are the same. - */ -#if MKFS_UBIFS_COMPR_NONE != UBIFS_COMPR_NONE -#error MKFS_UBIFS_COMPR_NONE != UBIFS_COMPR_NONE -#endif -#if MKFS_UBIFS_COMPR_LZO != UBIFS_COMPR_LZO -#error MKFS_UBIFS_COMPR_LZO != UBIFS_COMPR_LZO -#endif -#if MKFS_UBIFS_COMPR_ZLIB != UBIFS_COMPR_ZLIB -#error MKFS_UBIFS_COMPR_ZLIB != UBIFS_COMPR_ZLIB -#endif - -extern int verbose; -extern int debug_level; - -#define dbg_msg(lvl, fmt, ...) do {if (debug_level >= lvl) \ - printf("mkfs.ubifs: %s: " fmt "\n", __FUNCTION__, ##__VA_ARGS__); \ -} while(0) - -#define err_msg(fmt, ...) ({ \ - fprintf(stderr, "Error: " fmt "\n", ##__VA_ARGS__); \ - -1; \ -}) - -#define sys_err_msg(fmt, ...) ({ \ - int err_ = errno; \ - fprintf(stderr, "Error: " fmt "\n", ##__VA_ARGS__); \ - fprintf(stderr, " %s (error %d)\n", strerror(err_), err_); \ - -1; \ -}) - -/** - * struct path_htbl_element - an element of the path hash table. - * @path: the UBIFS path the element describes (the key of the element) - * @name_htbl: one more (nested) hash table containing names of all - * files/directories/device nodes which should be created at this - * path - * - * See device table handling for more information. - */ -struct path_htbl_element { - const char *path; - struct hashtable *name_htbl; -}; - -/** - * struct name_htbl_element - an element in the name hash table - * @name: name of the file/directory/device node (the key of the element) - * @mode: accsess rights and file type - * @uid: user ID - * @gid: group ID - * @major: device node major number - * @minor: device node minor number - * - * This is an element of the name hash table. Name hash table sits in the path - * hash table elements and describes file names which should be created/changed - * at this path. - */ -struct name_htbl_element { - const char *name; - unsigned int mode; - unsigned int uid; - unsigned int gid; - dev_t dev; -}; - -extern struct ubifs_info info_; - -struct hashtable_itr; - -int write_leb(int lnum, int len, void *buf); -int parse_devtable(const char *tbl_file); -struct path_htbl_element *devtbl_find_path(const char *path); -struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt, - const char *name); -int override_attributes(struct stat *st, struct path_htbl_element *ph_elt, - struct name_htbl_element *nh_elt); -struct name_htbl_element * -first_name_htbl_element(struct path_htbl_element *ph_elt, - struct hashtable_itr **itr); -struct name_htbl_element * -next_name_htbl_element(struct path_htbl_element *ph_elt, - struct hashtable_itr **itr); -void free_devtable_info(void); - -#endif diff --git a/mkfs.ubifs/ubifs.h b/mkfs.ubifs/ubifs.h deleted file mode 100644 index 434b651..0000000 --- a/mkfs.ubifs/ubifs.h +++ /dev/null @@ -1,441 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2008 Nokia Corporation. - * Copyright (C) 2008 University of Szeged, Hungary - * - * 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 - * Zoltan Sogor - */ - -#ifndef __UBIFS_H__ -#define __UBIFS_H__ - -/* Maximum logical eraseblock size in bytes */ -#define UBIFS_MAX_LEB_SZ (2*1024*1024) - -/* Minimum amount of data UBIFS writes to the flash */ -#define MIN_WRITE_SZ (UBIFS_DATA_NODE_SZ + 8) - -/* Largest key size supported in this implementation */ -#define CUR_MAX_KEY_LEN UBIFS_SK_LEN - -/* - * There is no notion of truncation key because truncation nodes do not exist - * in TNC. However, when replaying, it is handy to introduce fake "truncation" - * keys for truncation nodes because the code becomes simpler. So we define - * %UBIFS_TRUN_KEY type. - */ -#define UBIFS_TRUN_KEY UBIFS_KEY_TYPES_CNT - -/* The below union makes it easier to deal with keys */ -union ubifs_key -{ - uint8_t u8[CUR_MAX_KEY_LEN]; - uint32_t u32[CUR_MAX_KEY_LEN/4]; - uint64_t u64[CUR_MAX_KEY_LEN/8]; - __le32 j32[CUR_MAX_KEY_LEN/4]; -}; - -/* - * LEB properties flags. - * - * LPROPS_UNCAT: not categorized - * LPROPS_DIRTY: dirty > 0, not index - * LPROPS_DIRTY_IDX: dirty + free > UBIFS_CH_SZ and index - * LPROPS_FREE: free > 0, not empty, not index - * LPROPS_HEAP_CNT: number of heaps used for storing categorized LEBs - * LPROPS_EMPTY: LEB is empty, not taken - * LPROPS_FREEABLE: free + dirty == leb_size, not index, not taken - * LPROPS_FRDI_IDX: free + dirty == leb_size and index, may be taken - * LPROPS_CAT_MASK: mask for the LEB categories above - * LPROPS_TAKEN: LEB was taken (this flag is not saved on the media) - * LPROPS_INDEX: LEB contains indexing nodes (this flag also exists on flash) - */ -enum { - LPROPS_UNCAT = 0, - LPROPS_DIRTY = 1, - LPROPS_DIRTY_IDX = 2, - LPROPS_FREE = 3, - LPROPS_HEAP_CNT = 3, - LPROPS_EMPTY = 4, - LPROPS_FREEABLE = 5, - LPROPS_FRDI_IDX = 6, - LPROPS_CAT_MASK = 15, - LPROPS_TAKEN = 16, - LPROPS_INDEX = 32, -}; - -/** - * struct ubifs_lprops - logical eraseblock properties. - * @free: amount of free space in bytes - * @dirty: amount of dirty space in bytes - * @flags: LEB properties flags (see above) - */ -struct ubifs_lprops -{ - int free; - int dirty; - int flags; -}; - -/** - * struct ubifs_lpt_lprops - LPT logical eraseblock properties. - * @free: amount of free space in bytes - * @dirty: amount of dirty space in bytes - */ -struct ubifs_lpt_lprops -{ - int free; - int dirty; -}; - -struct ubifs_nnode; - -/** - * struct ubifs_cnode - LEB Properties Tree common node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (zero for pnodes, greater than zero for nnodes) - * @num: node number - */ -struct ubifs_cnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; -}; - -/** - * struct ubifs_pnode - LEB Properties Tree leaf node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (always zero for pnodes) - * @num: node number - * @lprops: LEB properties array - */ -struct ubifs_pnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; - struct ubifs_lprops lprops[UBIFS_LPT_FANOUT]; -}; - -/** - * struct ubifs_nbranch - LEB Properties Tree internal node branch. - * @lnum: LEB number of child - * @offs: offset of child - * @nnode: nnode child - * @pnode: pnode child - * @cnode: cnode child - */ -struct ubifs_nbranch -{ - int lnum; - int offs; - union - { - struct ubifs_nnode *nnode; - struct ubifs_pnode *pnode; - struct ubifs_cnode *cnode; - }; -}; - -/** - * struct ubifs_nnode - LEB Properties Tree internal node. - * @parent: parent nnode - * @cnext: next cnode to commit - * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE) - * @iip: index in parent - * @level: level in the tree (always greater than zero for nnodes) - * @num: node number - * @nbranch: branches to child nodes - */ -struct ubifs_nnode -{ - struct ubifs_nnode *parent; - struct ubifs_cnode *cnext; - unsigned long flags; - int iip; - int level; - int num; - struct ubifs_nbranch nbranch[UBIFS_LPT_FANOUT]; -}; - -/** - * struct ubifs_lp_stats - statistics of eraseblocks in the main area. - * @empty_lebs: number of empty LEBs - * @taken_empty_lebs: number of taken LEBs - * @idx_lebs: number of indexing LEBs - * @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) - */ -struct ubifs_lp_stats { - int empty_lebs; - int taken_empty_lebs; - int idx_lebs; - long long total_free; - long long total_dirty; - long long total_used; - long long total_dead; - long long total_dark; -}; - -/** - * struct ubifs_zbranch - key/coordinate/length branch stored in znodes. - * @key: key - * @znode: znode address in memory - * @lnum: LEB number of the indexing node - * @offs: offset of the indexing node within @lnum - * @len: target node length - */ -struct ubifs_zbranch -{ - union ubifs_key key; - struct ubifs_znode *znode; - int lnum; - int offs; - int len; -}; - -/** - * struct ubifs_znode - in-memory representation of an indexing node. - * @parent: parent znode or NULL if it is the root - * @cnext: next znode to commit - * @flags: flags - * @time: last access time (seconds) - * @level: level of the entry in the TNC tree - * @child_cnt: count of child znodes - * @iip: index in parent's zbranch array - * @alt: lower bound of key range has altered i.e. child inserted at slot 0 - * @zbranch: array of znode branches (@c->fanout elements) - */ -struct ubifs_znode -{ - struct ubifs_znode *parent; - struct ubifs_znode *cnext; - unsigned long flags; - unsigned long time; - int level; - int child_cnt; - int iip; - int alt; -#ifdef CONFIG_UBIFS_FS_DEBUG - int lnum, offs, len; -#endif - struct ubifs_zbranch zbranch[]; -}; - -/** - * struct ubifs_info - UBIFS file-system description data structure - * (per-superblock). - * - * @highest_inum: highest used inode number - * @max_sqnum: current global sequence number - * - * @jhead_cnt: count of journal heads - * @max_bud_bytes: maximum number of bytes allowed in buds - * - * @zroot: zbranch which points to the root index node and znode - * @ihead_lnum: LEB number of index head - * @ihead_offs: offset of index head - * - * @log_lebs: number of logical eraseblocks in the log - * @lpt_lebs: number of LEBs used for lprops table - * @lpt_first: first LEB of the lprops table area - * @lpt_last: last LEB of the lprops table area - * @main_lebs: count of LEBs in the main area - * @main_first: first LEB of the main area - * @default_compr: default compression type - * @favor_lzo: favor LZO compression method - * @favor_percent: lzo vs. zlib threshold used in case favor LZO - * - * @key_hash_type: type of the key hash - * @key_hash: direntry key hash function - * @key_fmt: key format - * @key_len: key length - * @fanout: fanout of the index tree (number of links per indexing node) - * - * @min_io_size: minimal input/output unit size - * @leb_size: logical eraseblock size in bytes - * @leb_cnt: count of logical eraseblocks - * @max_leb_cnt: maximum count of logical eraseblocks - * - * @old_idx_sz: size of index on flash - * @lst: lprops statistics - * - * @dead_wm: LEB dead space watermark - * @dark_wm: LEB dark space watermark - * - * @di: UBI device information - * @vi: UBI volume information - * - * @gc_lnum: LEB number used for garbage collection - * @rp_size: reserved pool size - * - * @space_bits: number of bits needed to record free or dirty space - * @lpt_lnum_bits: number of bits needed to record a LEB number in the LPT - * @lpt_offs_bits: number of bits needed to record an offset in the LPT - * @lpt_spc_bits: number of bits needed to space in the LPT - * @pcnt_bits: number of bits needed to record pnode or nnode number - * @lnum_bits: number of bits needed to record LEB number - * @nnode_sz: size of on-flash nnode - * @pnode_sz: size of on-flash pnode - * @ltab_sz: size of on-flash LPT lprops table - * @lsave_sz: size of on-flash LPT save table - * @pnode_cnt: number of pnodes - * @nnode_cnt: number of nnodes - * @lpt_hght: height of the LPT - * - * @lpt_lnum: LEB number of the root nnode of the LPT - * @lpt_offs: offset of the root nnode of the LPT - * @nhead_lnum: LEB number of LPT head - * @nhead_offs: offset of LPT head - * @big_lpt: flag that LPT is too big to write whole during commit - * @space_fixup: flag indicating that free space in LEBs needs to be cleaned up - * @lpt_sz: LPT size - * - * @ltab_lnum: LEB number of LPT's own lprops table - * @ltab_offs: offset of LPT's own lprops table - * @lpt: lprops table - * @ltab: LPT's own lprops table - * @lsave_cnt: number of LEB numbers in LPT's save table - * @lsave_lnum: LEB number of LPT's save table - * @lsave_offs: offset of LPT's save table - * @lsave: LPT's save table - * @lscan_lnum: LEB number of last LPT scan - */ -struct ubifs_info -{ - ino_t highest_inum; - unsigned long long max_sqnum; - - int jhead_cnt; - long long max_bud_bytes; - - struct ubifs_zbranch zroot; - int ihead_lnum; - int ihead_offs; - - int log_lebs; - int lpt_lebs; - int lpt_first; - int lpt_last; - int orph_lebs; - int main_lebs; - int main_first; - int default_compr; - int favor_lzo; - int favor_percent; - - uint8_t key_hash_type; - uint32_t (*key_hash)(const char *str, int len); - int key_fmt; - int key_len; - int fanout; - - int min_io_size; - int leb_size; - int leb_cnt; - int max_leb_cnt; - - unsigned long long old_idx_sz; - struct ubifs_lp_stats lst; - - int dead_wm; - int dark_wm; - - struct ubi_dev_info di; - struct ubi_vol_info vi; - - int gc_lnum; - long long rp_size; - - int space_bits; - int lpt_lnum_bits; - int lpt_offs_bits; - int lpt_spc_bits; - int pcnt_bits; - int lnum_bits; - int nnode_sz; - int pnode_sz; - int ltab_sz; - int lsave_sz; - int pnode_cnt; - int nnode_cnt; - int lpt_hght; - - int lpt_lnum; - int lpt_offs; - int nhead_lnum; - int nhead_offs; - int big_lpt; - int space_fixup; - long long lpt_sz; - - int ltab_lnum; - int ltab_offs; - struct ubifs_lprops *lpt; - struct ubifs_lpt_lprops *ltab; - int lsave_cnt; - int lsave_lnum; - int lsave_offs; - int *lsave; - int lscan_lnum; - -}; - -/** - * ubifs_idx_node_sz - return index node size. - * @c: the UBIFS file-system description object - * @child_cnt: number of children of this index node - */ -static inline int ubifs_idx_node_sz(const struct ubifs_info *c, int child_cnt) -{ - return UBIFS_IDX_NODE_SZ + (UBIFS_BRANCH_SZ + c->key_len) * child_cnt; -} - -/** - * ubifs_idx_branch - return pointer to an index branch. - * @c: the UBIFS file-system description object - * @idx: index node - * @bnum: branch number - */ -static inline -struct ubifs_branch *ubifs_idx_branch(const struct ubifs_info *c, - const struct ubifs_idx_node *idx, - int bnum) -{ - return (struct ubifs_branch *)((void *)idx->branches + - (UBIFS_BRANCH_SZ + c->key_len) * bnum); -} - -#endif /* __UBIFS_H__ */ -- cgit v1.2.3