diff --git a/tests/sys/cddl/zfs/tests/txg_integrity/fsync_integrity.c b/tests/sys/cddl/zfs/tests/txg_integrity/fsync_integrity.c index 17c6b63d45d8..5aba7a83225f 100644 --- a/tests/sys/cddl/zfs/tests/txg_integrity/fsync_integrity.c +++ b/tests/sys/cddl/zfs/tests/txg_integrity/fsync_integrity.c @@ -1,516 +1,516 @@ /* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2013 Spectra Logic. All rights reserved. * Use is subject to license terms. */ /* * Verify the integrity of non-aligned writes to the same blocks within the same * transaction group, where an fsync is issued by a non-final writer. * * This test verifies that the unoverride in the following sequence of events is * handled correctly: * * 1) A new transaction group opens * 2) A write is issued to a certain block * 3) The writer fsyncs() that file * 4) TBD module immediately writes that block, then places an override in the * syncer's TBD data structure, indicating that it doesn't need to write that * block when syncing. * 5) Another write is issued to the same block, with different data. * 6) TBD module unoverrides that block in the syncer's TBD data structure * 7) The syncer writes that block * * Outline: * Create a big zero-filled file. * Create a bunch of different IO patterns. Each IO pattern consists of: * * A partition of the file range into 64 different non-overlapping chunks. * * A permutation of those chunks * For each repetition: * For each IO pattern: * Create one binary semaphore per chunk, per (n-1) threads * Create n threads. * The first thread will write each chunk in order. It will post a * semaphore after each write to indicate that it has completed * writing that chunk. * The second thread will pend on those semaphores in order. Each time it * receives a semaphore, it will write a different pattern to that * chunk. Then it will post a different semaphore to signal the next * thread. * The final thread will not post any semaphores * Every even-numbered thread, starting with the first (0th), will fsync() * the file after its write. The final thread, being odd-numbered, * won't. * Join all threads * Read the entire file and verify that * 1) Every write went to the correct location * 2) The final thread's write is left in the file */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define NUM_REPETITIONS 16 #define CLUSTERSIZE (1 << 17) #define NUM_CHUNKS 64 #define FSIZE (64 * (CLUSTERSIZE)) //FSIZE may range from NUM_CHUNKS clusters to 8GB #define USE_THREADS 1 #define NUM_THREADS 8 typedef struct { //partitions describes the boundaries between chunks. Each element is a //fraction of the filesize in 1.31 fixed point format. So the boundary //between chunk n and chunk n-1 is (FSIZE * partitions[n-1] / (1<<31) . //partitions[-1] is understood to be 0 and partitions[NUM_CHUNKS] must be 1.0 //partitions is sorted, of course. //Partition boundaries must be dword aligned. Thus, in order to work with //multiple values of FSIZE, partitions values must be aligned to multiples of //8 / (NUM_CHUNKS * CLUSTERSIZE) = 1 / 524288 = 0x0.00002 uint32_t partitions[NUM_CHUNKS]; int permutation[NUM_CHUNKS]; //the order in which to write the chunks } pattern_t; typedef struct { int thread_num; - pattern_t* pat; + const pattern_t* pat; } thread_data_t; /* Returns (via begin and end) the range of a chunk. Begin is inclusive, * end is exclusive */ void get_chunk_range(const pattern_t* pat, int chunk, uint32_t* begin, uint32_t* end){ if (chunk == 0){ *begin = 0; } else{ *begin = (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk - 1] >> 31); } *end = (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk] >> 31); } /* The most basic, trivial IO pattern. Fully sequential, and the follower * writes every other block */ const pattern_t trivial_pattern = { {0x2000000, 0x4000000, 0x6000000, 0x8000000, 0xa000000, 0xc000000, 0xe000000, 0x10000000, 0x12000000, 0x14000000, 0x16000000, 0x18000000, 0x1a000000, 0x1c000000, 0x1e000000, 0x20000000, 0x22000000, 0x24000000, 0x26000000, 0x28000000, 0x2a000000, 0x2c000000, 0x2e000000, 0x30000000, 0x32000000, 0x34000000, 0x36000000, 0x38000000, 0x3a000000, 0x3c000000, 0x3e000000, 0x40000000, 0x42000000, 0x44000000, 0x46000000, 0x48000000, 0x4a000000, 0x4c000000, 0x4e000000, 0x50000000, 0x52000000, 0x54000000, 0x56000000, 0x58000000, 0x5a000000, 0x5c000000, 0x5e000000, 0x60000000, 0x62000000, 0x64000000, 0x66000000, 0x68000000, 0x6a000000, 0x6c000000, 0x6e000000, 0x70000000, 0x72000000, 0x74000000, 0x76000000, 0x78000000, 0x7a000000, 0x7c000000, 0x7e000000, 0x80000000}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63}, }; //The below patterns were randomly generated const pattern_t pat0 = { { 0x1eac000, 0x88a4000, 0xaffe000, 0xcdb7000, 0xd2d5000, 0xe16f000, 0xe499000, 0x11f71000, 0x1242d000, 0x12c07000, 0x143bc000, 0x1460a000, 0x15dd7000, 0x1700e000, 0x1be7e000, 0x1e14d000, 0x1e6ac000, 0x21097000, 0x24b74000, 0x27166000, 0x27669000, 0x30539000, 0x3218b000, 0x37591000, 0x37b60000, 0x39818000, 0x39d08000, 0x3c90e000, 0x3e54f000, 0x3fb99000, 0x42c8e000, 0x43a62000, 0x43f50000, 0x4c0c9000, 0x4c422000, 0x4c737000, 0x4d41e000, 0x4d738000, 0x4da71000, 0x4f4e8000, 0x508e3000, 0x51396000, 0x51ab5000, 0x52a02000, 0x54238000, 0x54d6a000, 0x55029000, 0x5584b000, 0x5c42c000, 0x5c4a7000, 0x5dac5000, 0x5fe4d000, 0x63f86000, 0x66ad0000, 0x67b3d000, 0x69ce5000, 0x6c179000, 0x6e79e000, 0x6f83f000, 0x71165000, 0x72bd9000, 0x7ac79000, 0x7dc94000, 0x80000000, }, { 57, 16, 28, 25, 10, 59, 52, 46, 30, 6, 40, 36, 39, 9, 21, 51, 33, 45, 44, 19, 2, 50, 55, 5, 58, 13, 23, 0, 12, 53, 42, 32, 31, 48, 35, 61, 49, 54, 18, 24, 8, 41, 62, 4, 47, 17, 1, 3, 34, 14, 63, 22, 15, 26, 38, 56, 27, 60, 29, 11, 7, 43, 20, 37, }, }; const pattern_t pat1 = { { 0x2b5000, 0x16db000, 0x5eb5000, 0x93a0000, 0xa7cb000, 0xa9e9000, 0xd144000, 0xe7c2000, 0xeb7d000, 0x10919000, 0x10cbd000, 0x11f85000, 0x17360000, 0x1760a000, 0x18eab000, 0x1ae6b000, 0x1c5f6000, 0x1df38000, 0x21bec000, 0x239d1000, 0x26b81000, 0x2747b000, 0x27a03000, 0x2b3cc000, 0x2cbf9000, 0x2ec0f000, 0x30a68000, 0x30bea000, 0x30c64000, 0x311af000, 0x35823000, 0x35d23000, 0x3b20e000, 0x405d8000, 0x414c8000, 0x43a91000, 0x44049000, 0x4ab4e000, 0x4ae21000, 0x4d293000, 0x511e5000, 0x516fc000, 0x52d77000, 0x57229000, 0x5da57000, 0x5dbe6000, 0x6070e000, 0x60fc0000, 0x64b24000, 0x67636000, 0x67658000, 0x6b040000, 0x6b28f000, 0x6e551000, 0x707c0000, 0x71b5c000, 0x72062000, 0x762a1000, 0x788a0000, 0x7a1e1000, 0x7b06a000, 0x7e04c000, 0x7f4cf000, 0x80000000, }, { 45, 8, 55, 9, 21, 54, 41, 7, 6, 22, 31, 47, 23, 11, 48, 53, 0, 61, 63, 50, 17, 27, 12, 19, 10, 40, 14, 51, 39, 59, 2, 43, 18, 42, 52, 28, 16, 44, 3, 5, 15, 35, 58, 33, 57, 49, 34, 30, 46, 4, 37, 60, 32, 36, 25, 56, 24, 13, 20, 38, 29, 26, 62, 1, }, }; const pattern_t pat2 = { { 0x912d000, 0xe610000, 0xf755000, 0x116df000, 0x128e5000, 0x1bd51000, 0x24e9a000, 0x27643000, 0x28cf4000, 0x292c9000, 0x2c907000, 0x2d389000, 0x2d941000, 0x2eb3f000, 0x30e94000, 0x31738000, 0x3343b000, 0x342ce000, 0x34d12000, 0x3536d000, 0x35e1a000, 0x35e4d000, 0x35fd5000, 0x3642b000, 0x3924d000, 0x392a5000, 0x3e531000, 0x3f0ee000, 0x3fdf8000, 0x41593000, 0x41c80000, 0x43959000, 0x43bc0000, 0x461c8000, 0x48922000, 0x49519000, 0x4f6fa000, 0x50274000, 0x508ae000, 0x536ed000, 0x54154000, 0x59894000, 0x5a666000, 0x5b0a6000, 0x5b9ff000, 0x5c109000, 0x5d8d0000, 0x5ddc5000, 0x5fcc5000, 0x63366000, 0x63adc000, 0x645b6000, 0x670eb000, 0x6b1b1000, 0x6c996000, 0x6ed2a000, 0x6ee4f000, 0x71fcd000, 0x734a3000, 0x76bdf000, 0x77b3f000, 0x7c65a000, 0x7d200000, 0x80000000, }, { 31, 35, 36, 52, 27, 56, 40, 13, 51, 49, 43, 37, 62, 42, 24, 29, 48, 25, 7, 61, 22, 57, 11, 32, 2, 54, 41, 6, 55, 15, 20, 26, 63, 44, 12, 4, 19, 58, 60, 59, 47, 23, 30, 50, 53, 34, 9, 38, 45, 8, 28, 3, 16, 33, 5, 21, 1, 10, 46, 18, 0, 14, 39, 17, }, }; const pattern_t pat3 = { { 0x553000, 0x19de000, 0x6a20000, 0x8a53000, 0x8ef9000, 0xc325000, 0x1132e000, 0x139fa000, 0x1426b000, 0x150ff000, 0x1bbc1000, 0x1e84c000, 0x1f43e000, 0x1f731000, 0x21ec8000, 0x231f4000, 0x23440000, 0x23466000, 0x260b6000, 0x286a7000, 0x29518000, 0x29e35000, 0x2fdb7000, 0x3089d000, 0x362e0000, 0x3c1f9000, 0x3df2d000, 0x3fce6000, 0x402f3000, 0x4117f000, 0x41e06000, 0x4374f000, 0x451e5000, 0x45a59000, 0x4956b000, 0x4960f000, 0x4a934000, 0x4bc6f000, 0x4d462000, 0x4eef8000, 0x4f609000, 0x50dc1000, 0x51022000, 0x54396000, 0x5641b000, 0x578f1000, 0x589cf000, 0x59093000, 0x5da6b000, 0x5fbf0000, 0x605a2000, 0x65428000, 0x65530000, 0x6705a000, 0x6db65000, 0x71cef000, 0x725a2000, 0x73bf5000, 0x75acb000, 0x76065000, 0x7614c000, 0x77aab000, 0x78f70000, 0x80000000, }, { 15, 30, 31, 16, 49, 13, 55, 59, 4, 24, 26, 44, 17, 0, 18, 54, 10, 3, 46, 34, 29, 22, 45, 5, 38, 32, 39, 50, 48, 53, 12, 25, 35, 56, 51, 52, 1, 33, 43, 63, 47, 37, 23, 20, 60, 14, 11, 21, 8, 57, 27, 41, 6, 58, 62, 2, 19, 61, 28, 36, 40, 7, 9, 42, }, }; const pattern_t pat4 = { { 0x425000, 0x8e8000, 0x4b90000, 0x883c000, 0x968e000, 0xbacc000, 0x10e59000, 0x125a1000, 0x12f00000, 0x14e7c000, 0x156de000, 0x192a1000, 0x1a2b9000, 0x1b4a0000, 0x1be9c000, 0x1d3bd000, 0x24242000, 0x2516b000, 0x2b88d000, 0x2b96a000, 0x2bcd3000, 0x2c5a9000, 0x2da74000, 0x2dba1000, 0x3097f000, 0x332ef000, 0x34525000, 0x36193000, 0x3725c000, 0x37e66000, 0x3d315000, 0x3e813000, 0x404ae000, 0x40c68000, 0x42f93000, 0x44b14000, 0x44b15000, 0x473b2000, 0x49048000, 0x4c794000, 0x50b60000, 0x52b3d000, 0x58c61000, 0x5b7d4000, 0x5ce71000, 0x5d21d000, 0x5d63e000, 0x5e00f000, 0x60e8b000, 0x66381000, 0x66c70000, 0x68430000, 0x707c2000, 0x71979000, 0x72681000, 0x74017000, 0x7721d000, 0x7a1be000, 0x7a2cd000, 0x7b225000, 0x7c311000, 0x7e03a000, 0x7e402000, 0x80000000, }, { 52, 62, 28, 47, 51, 37, 31, 36, 4, 58, 26, 29, 16, 59, 57, 33, 22, 27, 49, 44, 19, 56, 34, 23, 5, 14, 45, 48, 21, 25, 18, 12, 43, 53, 60, 17, 46, 15, 63, 30, 42, 38, 41, 8, 39, 20, 1, 10, 54, 40, 32, 24, 9, 2, 35, 3, 7, 0, 61, 11, 13, 55, 6, 50, }, }; const pattern_t pat5 = { { 0xae7000, 0x436e000, 0x81e1000, 0xb276000, 0xf8bf000, 0xfb26000, 0xfe7e000, 0x137ad000, 0x14b8e000, 0x157aa000, 0x1981a000, 0x1a32f000, 0x1bc9e000, 0x1def5000, 0x1e8ef000, 0x2068f000, 0x22692000, 0x22a6c000, 0x255bf000, 0x26977000, 0x27619000, 0x2977c000, 0x2ce0c000, 0x2e1ec000, 0x2e26c000, 0x31ce8000, 0x34e6c000, 0x365cd000, 0x37e87000, 0x385e3000, 0x3a7e2000, 0x3a9c7000, 0x41597000, 0x42e8a000, 0x453cc000, 0x454bf000, 0x4b24c000, 0x4ba54000, 0x4e307000, 0x4f059000, 0x55d5a000, 0x56277000, 0x56b90000, 0x5882d000, 0x5a2c5000, 0x5b369000, 0x5d442000, 0x5d671000, 0x5fdd0000, 0x60ce0000, 0x63713000, 0x64130000, 0x65973000, 0x67ad9000, 0x68764000, 0x68bb2000, 0x690d1000, 0x6a2c8000, 0x73e9f000, 0x74e75000, 0x77861000, 0x77ee5000, 0x7cddb000, 0x80000000, }, { 42, 25, 15, 58, 32, 61, 30, 56, 48, 62, 38, 50, 7, 45, 16, 29, 12, 4, 41, 3, 27, 18, 57, 10, 51, 17, 21, 14, 35, 19, 44, 47, 49, 26, 59, 63, 28, 55, 20, 13, 5, 6, 37, 54, 40, 22, 23, 46, 11, 36, 34, 31, 2, 60, 9, 52, 24, 1, 53, 0, 39, 43, 8, 33, }, }; const pattern_t pat6 = { { 0xad2000, 0x222f000, 0x64b4000, 0x6c66000, 0x6f35000, 0x9e50000, 0xe744000, 0xf129000, 0x101bb000, 0x11bf8000, 0x14b89000, 0x1691c000, 0x17a0d000, 0x1817a000, 0x1997a000, 0x1d736000, 0x1db33000, 0x1fdd8000, 0x21e56000, 0x2266c000, 0x22875000, 0x22b84000, 0x230ed000, 0x239c5000, 0x24e1a000, 0x275f5000, 0x29036000, 0x29f69000, 0x2e538000, 0x2efca000, 0x2f0bc000, 0x2f1bf000, 0x305cb000, 0x31ce7000, 0x345c4000, 0x35d4f000, 0x36e56000, 0x3ae9e000, 0x3cc27000, 0x40117000, 0x4299f000, 0x434c3000, 0x443d4000, 0x4552d000, 0x4a8a8000, 0x4cdea000, 0x51bd5000, 0x580c4000, 0x58381000, 0x59dc0000, 0x5ba7f000, 0x5d88b000, 0x5e0c4000, 0x5ee57000, 0x61f3f000, 0x63a4a000, 0x68a8a000, 0x68ec5000, 0x6937b000, 0x720be000, 0x72cf5000, 0x74fc8000, 0x76464000, 0x80000000, }, { 31, 46, 36, 22, 63, 12, 51, 60, 13, 44, 41, 6, 11, 17, 42, 24, 16, 61, 20, 26, 35, 21, 29, 55, 50, 45, 62, 19, 54, 9, 30, 34, 53, 52, 10, 39, 0, 49, 48, 38, 40, 28, 23, 56, 2, 5, 4, 59, 14, 57, 3, 25, 43, 32, 27, 47, 8, 7, 37, 33, 1, 18, 58, 15, }, }; const pattern_t pat7 = { { 0xd83000, 0x1597000, 0x245b000, 0x6a75000, 0x8fda000, 0x960e000, 0xd310000, 0xe6cd000, 0x1409a000, 0x15221000, 0x16059000, 0x1b3a4000, 0x1ceea000, 0x1ed1a000, 0x1ef0f000, 0x21723000, 0x21efc000, 0x24594000, 0x26d7f000, 0x28c4f000, 0x2fa89000, 0x304f0000, 0x30dbb000, 0x30de3000, 0x3365d000, 0x36dbc000, 0x3acb2000, 0x3e291000, 0x3f7da000, 0x41352000, 0x41a0f000, 0x435c8000, 0x4475a000, 0x47536000, 0x47726000, 0x4a81f000, 0x4be4e000, 0x4bf05000, 0x4c15b000, 0x515b4000, 0x52ef5000, 0x548cc000, 0x5692a000, 0x59ef2000, 0x5b97c000, 0x5c4f0000, 0x5d1b9000, 0x618ed000, 0x61bcc000, 0x61e07000, 0x639a3000, 0x65302000, 0x68041000, 0x6be56000, 0x721a3000, 0x72c99000, 0x740b9000, 0x7586d000, 0x75eca000, 0x76406000, 0x7b68a000, 0x7dd26000, 0x7ed55000, 0x80000000, }, { 44, 57, 22, 35, 63, 11, 15, 49, 61, 40, 29, 20, 19, 42, 32, 12, 41, 6, 46, 60, 52, 5, 36, 10, 2, 8, 3, 33, 54, 39, 58, 48, 62, 7, 51, 34, 0, 1, 18, 9, 55, 31, 23, 38, 25, 21, 17, 24, 13, 50, 16, 14, 43, 53, 45, 28, 59, 37, 26, 30, 47, 27, 56, 4, }, }; const pattern_t pat8 = { { 0x1b8000, 0x27eb000, 0x5a4d000, 0x6ecc000, 0xb52e000, 0xb70e000, 0xc6db000, 0xd83d000, 0xed51000, 0x13c59000, 0x13fef000, 0x142e1000, 0x192d0000, 0x1aa63000, 0x1e230000, 0x1f464000, 0x20de4000, 0x2234b000, 0x25459000, 0x27018000, 0x28263000, 0x29cc7000, 0x32227000, 0x32c63000, 0x34af0000, 0x37e27000, 0x3afc9000, 0x3c166000, 0x3df20000, 0x405bd000, 0x41273000, 0x45c39000, 0x471be000, 0x4758e000, 0x4b3fc000, 0x4c6b2000, 0x4c80f000, 0x4ccd6000, 0x4d9e0000, 0x4e07f000, 0x4eeda000, 0x541ae000, 0x58aa7000, 0x5a2c6000, 0x5a628000, 0x5ab94000, 0x5bddc000, 0x5d1d4000, 0x5e643000, 0x5f72f000, 0x64771000, 0x67bd4000, 0x6a28c000, 0x6c977000, 0x6cc4e000, 0x710c4000, 0x74b86000, 0x75cf7000, 0x77d4b000, 0x7870e000, 0x7c47c000, 0x7eb52000, 0x7fbea000, 0x80000000, }, { 7, 29, 62, 8, 54, 38, 35, 45, 60, 55, 1, 40, 4, 19, 50, 63, 48, 51, 13, 27, 33, 39, 52, 46, 10, 9, 56, 2, 42, 43, 47, 44, 17, 5, 25, 6, 57, 23, 15, 58, 59, 22, 14, 26, 32, 61, 30, 0, 11, 12, 36, 24, 53, 49, 3, 20, 31, 28, 34, 18, 41, 21, 16, 37, }, }; const pattern_t pat9 = { { 0x5b59000, 0xa6d7000, 0xbad3000, 0xdf91000, 0x115ad000, 0x13fde000, 0x17618000, 0x1b8e9000, 0x1e1b7000, 0x1e97d000, 0x21737000, 0x21a5e000, 0x24140000, 0x2558f000, 0x2647a000, 0x28257000, 0x285f6000, 0x2cb7a000, 0x2ebb1000, 0x30ae8000, 0x31543000, 0x315cb000, 0x31616000, 0x335ba000, 0x33ed6000, 0x35cf3000, 0x4162b000, 0x4409b000, 0x4629a000, 0x4b745000, 0x4c0ba000, 0x4cbc5000, 0x4dd97000, 0x4f34b000, 0x4f637000, 0x539d6000, 0x53f3d000, 0x56383000, 0x5642b000, 0x5a71f000, 0x5affa000, 0x5b486000, 0x5b8ef000, 0x60d88000, 0x61629000, 0x625cd000, 0x63326000, 0x6735e000, 0x67379000, 0x6a26a000, 0x6a281000, 0x6b997000, 0x6c50d000, 0x6cc6c000, 0x6f496000, 0x717ad000, 0x732ec000, 0x744dc000, 0x771e8000, 0x77cf0000, 0x79cad000, 0x7bb21000, 0x7e7b4000, 0x80000000, }, { 35, 9, 46, 6, 29, 2, 3, 54, 55, 57, 41, 16, 44, 5, 0, 59, 10, 61, 22, 42, 47, 12, 14, 50, 39, 34, 21, 32, 25, 15, 26, 8, 38, 60, 28, 53, 62, 49, 58, 43, 36, 37, 52, 7, 19, 63, 17, 11, 45, 33, 23, 27, 24, 18, 48, 56, 31, 13, 51, 30, 4, 20, 40, 1, }, }; const pattern_t pat10 = { { 0xa72000, 0x180a000, 0x6406000, 0x66df000, 0x83bb000, 0xa96f000, 0xd193000, 0x13b9b000, 0x13dae000, 0x16109000, 0x1853d000, 0x18887000, 0x19f0a000, 0x22151000, 0x229ba000, 0x26b58000, 0x2aaf4000, 0x2bf50000, 0x31a2e000, 0x31d4e000, 0x32196000, 0x3513a000, 0x36a2d000, 0x3746b000, 0x389ad000, 0x39d27000, 0x3dad3000, 0x3de55000, 0x3ea9b000, 0x3ec06000, 0x3f921000, 0x432d3000, 0x43bec000, 0x43dda000, 0x47b2b000, 0x4886e000, 0x4928e000, 0x49ad2000, 0x4d0df000, 0x4f40d000, 0x50959000, 0x54fa4000, 0x56091000, 0x5688d000, 0x5b7d8000, 0x5f6fd000, 0x601e4000, 0x64eaa000, 0x6752e000, 0x67fff000, 0x6a184000, 0x6ad7a000, 0x6adbc000, 0x6c434000, 0x6f451000, 0x6ffb4000, 0x707ee000, 0x71161000, 0x7146b000, 0x75dbf000, 0x77259000, 0x7acd4000, 0x7af71000, 0x80000000, }, { 61, 38, 5, 23, 62, 11, 53, 9, 17, 45, 30, 29, 41, 60, 39, 21, 40, 19, 44, 33, 42, 50, 56, 28, 32, 46, 43, 20, 16, 3, 54, 8, 4, 26, 15, 34, 47, 12, 6, 27, 48, 0, 1, 2, 57, 59, 7, 58, 49, 35, 24, 37, 52, 63, 10, 55, 36, 13, 14, 25, 18, 22, 31, 51, }, }; const pattern_t pat11 = { { 0x996000, 0xaff000, 0x199a000, 0x46f3000, 0x74c0000, 0x758d000, 0xcd09000, 0xe48c000, 0xe8de000, 0xf111000, 0xf87b000, 0x10b1c000, 0x15d63000, 0x17b21000, 0x182d3000, 0x19167000, 0x198ce000, 0x1bd47000, 0x1dff1000, 0x1edc0000, 0x1f890000, 0x20860000, 0x23207000, 0x29bd5000, 0x2ac0f000, 0x2e395000, 0x2e707000, 0x329de000, 0x3497f000, 0x3807f000, 0x38a94000, 0x40a19000, 0x4168e000, 0x42ca0000, 0x42de9000, 0x45194000, 0x464f2000, 0x4700f000, 0x47dbb000, 0x4dae7000, 0x50660000, 0x535a8000, 0x5546b000, 0x57b55000, 0x5860a000, 0x5a9ee000, 0x5b8d9000, 0x5c49f000, 0x5cb4d000, 0x5d28c000, 0x60dcd000, 0x62557000, 0x64b0c000, 0x654cb000, 0x65746000, 0x65e29000, 0x6648f000, 0x66c56000, 0x6999e000, 0x6a11c000, 0x6ca04000, 0x79e60000, 0x7edce000, 0x80000000, }, { 16, 28, 2, 38, 10, 57, 21, 26, 61, 43, 46, 31, 56, 7, 47, 48, 58, 25, 63, 4, 59, 15, 32, 50, 1, 40, 53, 18, 17, 24, 29, 30, 55, 36, 49, 42, 41, 37, 23, 39, 6, 51, 33, 9, 45, 5, 35, 19, 44, 11, 34, 0, 27, 12, 60, 62, 20, 13, 22, 8, 14, 54, 3, 52, }, }; const pattern_t pat12 = { { 0x513000, 0x1b72000, 0x1e27000, 0x3a63000, 0x1115c000, 0x158b4000, 0x1664f000, 0x1b667000, 0x1f838000, 0x21410000, 0x260c7000, 0x2cd8f000, 0x2ce37000, 0x2df16000, 0x2e59e000, 0x2e8eb000, 0x2ebd2000, 0x2f1d2000, 0x2fc42000, 0x30d00000, 0x31ef1000, 0x3301a000, 0x38097000, 0x38a1e000, 0x3d818000, 0x3e898000, 0x3f90f000, 0x47710000, 0x478bb000, 0x485ab000, 0x48e54000, 0x4cfe1000, 0x53a89000, 0x53d10000, 0x56308000, 0x56f3b000, 0x577f6000, 0x58734000, 0x5889b000, 0x58ad7000, 0x5923a000, 0x59aef000, 0x5dad3000, 0x5e32f000, 0x63b3a000, 0x665c9000, 0x68cde000, 0x69252000, 0x6a777000, 0x6a79a000, 0x6c1f0000, 0x6cb9a000, 0x6d319000, 0x6dc82000, 0x6dd4d000, 0x6e188000, 0x7184d000, 0x7206e000, 0x73980000, 0x740ad000, 0x75473000, 0x7614d000, 0x79b17000, 0x80000000, }, { 4, 60, 10, 35, 6, 31, 5, 18, 53, 17, 20, 8, 56, 29, 7, 48, 40, 0, 12, 39, 2, 43, 15, 61, 42, 30, 50, 14, 49, 38, 34, 58, 24, 55, 33, 63, 28, 51, 59, 46, 11, 22, 45, 41, 13, 44, 23, 47, 3, 32, 16, 54, 26, 19, 25, 52, 27, 57, 36, 9, 37, 21, 62, 1, }, }; const pattern_t pat13 = { { 0x351e000, 0x5917000, 0xa992000, 0xc471000, 0xc69c000, 0xc6ed000, 0xc919000, 0xd713000, 0xec14000, 0xfa31000, 0x17567000, 0x1d81a000, 0x1f3c8000, 0x215b5000, 0x26e41000, 0x2a2d4000, 0x2b750000, 0x2bea0000, 0x2c5ae000, 0x2ca2c000, 0x30a94000, 0x31074000, 0x314d3000, 0x31b1e000, 0x31de2000, 0x32062000, 0x33da5000, 0x37838000, 0x385ec000, 0x38740000, 0x387f9000, 0x38be6000, 0x3d2f7000, 0x3eaf5000, 0x40266000, 0x402f3000, 0x40fda000, 0x4a4bd000, 0x4b831000, 0x4bfc9000, 0x4ccaa000, 0x4ea43000, 0x50190000, 0x547c8000, 0x58cc6000, 0x58ea5000, 0x59de1000, 0x5c7f1000, 0x5f713000, 0x63f9a000, 0x6686d000, 0x675c1000, 0x6cccc000, 0x6e409000, 0x6fb6d000, 0x71a70000, 0x72f60000, 0x77bd9000, 0x79013000, 0x7a8d3000, 0x7b341000, 0x7d8f7000, 0x7fe43000, 0x80000000, }, { 10, 52, 48, 8, 34, 4, 35, 19, 3, 17, 54, 45, 31, 38, 24, 44, 21, 36, 22, 11, 43, 40, 39, 26, 5, 30, 2, 7, 57, 12, 20, 32, 62, 15, 55, 14, 25, 58, 6, 33, 49, 9, 59, 27, 13, 63, 42, 61, 1, 51, 0, 50, 37, 47, 16, 18, 41, 56, 60, 46, 23, 28, 53, 29, }, }; const pattern_t pat14 = { { 0xf8e000, 0x169a000, 0x3816000, 0x67a9000, 0x89f3000, 0xac97000, 0xc8da000, 0xf077000, 0x119f1000, 0x13902000, 0x19785000, 0x1ca7f000, 0x1f958000, 0x2027d000, 0x2251f000, 0x24661000, 0x25604000, 0x2b924000, 0x2be5f000, 0x2ec27000, 0x330a5000, 0x3349e000, 0x33a84000, 0x344fa000, 0x34514000, 0x37966000, 0x37f0b000, 0x37fcd000, 0x386d0000, 0x39600000, 0x39de4000, 0x3e601000, 0x3e7f1000, 0x42c61000, 0x48806000, 0x4d3d0000, 0x4f5ff000, 0x512c1000, 0x53fd4000, 0x59440000, 0x5b386000, 0x5e8a0000, 0x5fca3000, 0x6016c000, 0x61ca8000, 0x64915000, 0x66b99000, 0x67226000, 0x69b2f000, 0x6a473000, 0x6a590000, 0x6c844000, 0x6cb8c000, 0x713b5000, 0x7558a000, 0x75eab000, 0x76d15000, 0x77efe000, 0x78762000, 0x7bddc000, 0x7ce92000, 0x7dc44000, 0x7f54b000, 0x80000000, }, { 54, 31, 48, 10, 51, 49, 55, 19, 38, 18, 44, 5, 17, 20, 16, 11, 9, 3, 42, 59, 63, 45, 25, 60, 57, 21, 40, 29, 0, 39, 26, 7, 53, 12, 13, 2, 58, 41, 22, 8, 14, 28, 46, 24, 27, 6, 52, 32, 56, 4, 30, 36, 15, 47, 23, 37, 43, 35, 50, 33, 61, 34, 1, 62, }, }; const pattern_t pat15 = { { 0xe16000, 0xec6000, 0xf6b000, 0x634b000, 0x6896000, 0x91db000, 0xc2c8000, 0xe083000, 0xfd7f000, 0x10479000, 0x17740000, 0x18292000, 0x1aaca000, 0x1cb55000, 0x1d2be000, 0x222af000, 0x2cb03000, 0x2fabc000, 0x32034000, 0x35c0f000, 0x3c5ec000, 0x40908000, 0x4128e000, 0x44411000, 0x44bcd000, 0x4f0ac000, 0x5167b000, 0x5541c000, 0x581bc000, 0x584e5000, 0x588fb000, 0x593d3000, 0x5b25d000, 0x5dc99000, 0x60b35000, 0x60ffc000, 0x638e8000, 0x63cf8000, 0x64ee1000, 0x6523c000, 0x654a1000, 0x687bf000, 0x68bef000, 0x69826000, 0x69d90000, 0x6a622000, 0x6d1b9000, 0x6d1e1000, 0x6d886000, 0x6fe4a000, 0x6feac000, 0x720b2000, 0x734dc000, 0x73530000, 0x73f1e000, 0x7479c000, 0x76e33000, 0x786dc000, 0x79b40000, 0x79e49000, 0x7b66c000, 0x7b904000, 0x7c906000, 0x80000000, }, { 6, 17, 62, 20, 61, 32, 22, 14, 28, 18, 3, 42, 63, 43, 46, 34, 29, 30, 35, 1, 37, 40, 10, 26, 5, 31, 15, 54, 8, 33, 9, 4, 39, 53, 23, 25, 41, 59, 12, 13, 60, 2, 7, 56, 58, 27, 11, 38, 36, 45, 47, 0, 57, 50, 48, 16, 51, 49, 55, 52, 44, 24, 19, 21, }, }; const pattern_t pat16 = { { 0x596a000, 0x8644000, 0xa943000, 0xd59e000, 0x1062f000, 0x1082a000, 0x10c1b000, 0x10f9e000, 0x11e64000, 0x12e73000, 0x15ce7000, 0x16037000, 0x16d2e000, 0x17035000, 0x185ad000, 0x18d9b000, 0x19ac7000, 0x1b2fa000, 0x1cd6c000, 0x1d5f0000, 0x1f72c000, 0x20891000, 0x24bfa000, 0x25c1d000, 0x28e24000, 0x2a5f8000, 0x2e0ae000, 0x2fddf000, 0x3119d000, 0x332ee000, 0x3480a000, 0x34ea5000, 0x3534e000, 0x3538b000, 0x362e2000, 0x38f58000, 0x39ab0000, 0x3a519000, 0x3a62b000, 0x3b006000, 0x3d523000, 0x3e0f7000, 0x42366000, 0x42feb000, 0x44013000, 0x46b98000, 0x49794000, 0x4dce7000, 0x4f1f3000, 0x57ecd000, 0x5aaa2000, 0x5f419000, 0x61517000, 0x6797d000, 0x69a20000, 0x6a070000, 0x70575000, 0x75322000, 0x75a9e000, 0x79043000, 0x79875000, 0x7addc000, 0x7de88000, 0x80000000, }, { 26, 25, 6, 50, 32, 53, 34, 27, 3, 16, 49, 28, 46, 38, 56, 4, 18, 24, 51, 36, 63, 5, 48, 13, 43, 55, 0, 62, 35, 7, 41, 21, 44, 60, 31, 39, 14, 8, 61, 58, 52, 23, 59, 33, 10, 37, 20, 30, 40, 22, 11, 54, 57, 1, 29, 47, 2, 17, 19, 45, 15, 9, 12, 42, }, }; const pattern_t pat17 = { { 0x28ab000, 0x3ac8000, 0x3fe1000, 0x63a7000, 0x90fc000, 0xb3f2000, 0xd2f2000, 0xe032000, 0x12d4c000, 0x13135000, 0x14652000, 0x15331000, 0x1570c000, 0x1688e000, 0x16bc3000, 0x1cbe3000, 0x1fe0f000, 0x2517f000, 0x26c6b000, 0x2a284000, 0x2a4e2000, 0x2add5000, 0x2bd06000, 0x2ca3a000, 0x2eb11000, 0x324d1000, 0x35662000, 0x38695000, 0x38ce7000, 0x391ac000, 0x398f9000, 0x39949000, 0x401f3000, 0x457f0000, 0x45c6d000, 0x4b561000, 0x522fc000, 0x54ef0000, 0x559f8000, 0x562a7000, 0x56a04000, 0x57b68000, 0x59702000, 0x5ffc9000, 0x63a76000, 0x63c37000, 0x65d3e000, 0x67130000, 0x6a03a000, 0x6bcd6000, 0x6be96000, 0x6bf52000, 0x6fcd9000, 0x7038c000, 0x70a47000, 0x72881000, 0x72ed0000, 0x75035000, 0x75c11000, 0x77fa5000, 0x797c9000, 0x79813000, 0x7bbbb000, 0x80000000, }, { 18, 15, 56, 5, 25, 47, 39, 55, 12, 14, 51, 33, 0, 7, 9, 44, 50, 31, 62, 59, 3, 35, 23, 17, 30, 60, 11, 24, 40, 20, 52, 2, 22, 8, 57, 42, 32, 54, 36, 48, 49, 13, 58, 10, 28, 63, 16, 41, 27, 21, 37, 4, 1, 29, 19, 6, 53, 45, 46, 38, 34, 43, 61, 26, }, }; const pattern_t pat18 = { { 0x38d6000, 0x5379000, 0x5cae000, 0x5d20000, 0xa248000, 0xb4d0000, 0xd7c0000, 0xf731000, 0x116ae000, 0x151d2000, 0x1747d000, 0x1bfb6000, 0x1d758000, 0x2053d000, 0x24dda000, 0x25274000, 0x269c0000, 0x273e8000, 0x2a5d0000, 0x2ad34000, 0x3016b000, 0x30d1a000, 0x32960000, 0x34b3b000, 0x36e4f000, 0x37934000, 0x38c42000, 0x3c2d2000, 0x3d23d000, 0x3d89a000, 0x3dc85000, 0x3e9a7000, 0x3f25b000, 0x45bd1000, 0x48d94000, 0x4b126000, 0x4e17c000, 0x4f377000, 0x50908000, 0x51957000, 0x53410000, 0x5412c000, 0x55256000, 0x56b17000, 0x5707b000, 0x5bbe5000, 0x5d067000, 0x5e1c1000, 0x6380b000, 0x66009000, 0x68240000, 0x69fc4000, 0x6c327000, 0x6c5d2000, 0x6f69d000, 0x739c7000, 0x744bc000, 0x74cd8000, 0x787b8000, 0x78c61000, 0x7969d000, 0x79aae000, 0x7b032000, 0x80000000, }, { 16, 48, 50, 60, 13, 39, 20, 4, 63, 18, 14, 30, 55, 8, 62, 37, 43, 41, 11, 0, 36, 33, 34, 49, 17, 58, 38, 22, 19, 5, 21, 12, 47, 25, 57, 61, 7, 3, 10, 23, 52, 24, 6, 53, 2, 26, 1, 31, 28, 46, 42, 9, 45, 29, 27, 54, 32, 56, 51, 44, 35, 59, 40, 15, }, }; const pattern_t pat19 = { { 0x297d000, 0x34e0000, 0x7801000, 0x9664000, 0x96fa000, 0xbb9f000, 0xc192000, 0xc4a5000, 0xca74000, 0xcce8000, 0x173d8000, 0x1a8d8000, 0x1b299000, 0x1b52d000, 0x1e813000, 0x2185e000, 0x21abe000, 0x2b9a4000, 0x2c4b6000, 0x2fa27000, 0x343ba000, 0x356fd000, 0x37c6e000, 0x38365000, 0x3a9e4000, 0x3b599000, 0x4296b000, 0x43196000, 0x4381e000, 0x44783000, 0x47a75000, 0x4bd78000, 0x4d05d000, 0x4edb2000, 0x4eefd000, 0x4fecc000, 0x51f68000, 0x5252b000, 0x5439e000, 0x55fb3000, 0x5814f000, 0x5939d000, 0x60a78000, 0x62a86000, 0x633b0000, 0x64a68000, 0x64b62000, 0x66207000, 0x66540000, 0x67f90000, 0x68bf3000, 0x6a069000, 0x6d2ac000, 0x70c9f000, 0x71bab000, 0x724bc000, 0x783d8000, 0x7900e000, 0x79399000, 0x79763000, 0x7c8a8000, 0x7e680000, 0x7f6de000, 0x80000000, }, { 14, 59, 60, 24, 18, 22, 62, 12, 45, 2, 32, 11, 25, 37, 13, 7, 50, 39, 56, 17, 47, 40, 29, 43, 15, 34, 4, 57, 31, 38, 21, 28, 36, 27, 42, 1, 23, 33, 5, 61, 44, 55, 8, 30, 10, 41, 19, 48, 16, 52, 49, 46, 54, 58, 6, 0, 51, 3, 26, 20, 53, 9, 35, 63, }, }; const pattern_t pat20 = { { 0x8f7000, 0xa01000, 0x38e3000, 0x5299000, 0x6875000, 0x7f3e000, 0x827f000, 0x9413000, 0xca71000, 0xfb11000, 0x10beb000, 0x176be000, 0x1924f000, 0x1cfd6000, 0x1d20d000, 0x1ebb7000, 0x22c93000, 0x23601000, 0x2cf7a000, 0x2d3af000, 0x2e391000, 0x2f294000, 0x318ad000, 0x34ddd000, 0x365e4000, 0x3b8d2000, 0x3c0f8000, 0x3d2fd000, 0x3e431000, 0x3f0fe000, 0x4074e000, 0x40d1c000, 0x41936000, 0x4347b000, 0x452d7000, 0x486d3000, 0x4b47e000, 0x4b709000, 0x4c349000, 0x4ff13000, 0x50faa000, 0x51a07000, 0x52f30000, 0x55f29000, 0x57ad4000, 0x5909f000, 0x5a0f6000, 0x5de57000, 0x60d2f000, 0x625ff000, 0x6288e000, 0x65077000, 0x6a707000, 0x6a73f000, 0x6d720000, 0x6e390000, 0x6edc9000, 0x6ee78000, 0x77ac2000, 0x77ad3000, 0x7868f000, 0x79a1b000, 0x7aec6000, 0x80000000, }, { 21, 56, 38, 11, 62, 9, 30, 47, 34, 23, 37, 16, 5, 49, 10, 43, 4, 45, 36, 7, 42, 1, 53, 57, 20, 59, 55, 50, 46, 39, 60, 27, 12, 31, 48, 25, 15, 22, 44, 52, 14, 33, 0, 29, 17, 18, 2, 32, 24, 19, 6, 41, 54, 8, 35, 26, 61, 3, 51, 13, 63, 28, 40, 58, }, }; const pattern_t pat21 = { { 0x2a8e000, 0xa4bd000, 0xa935000, 0xcc05000, 0xdfe4000, 0xe014000, 0xff46000, 0x18c8c000, 0x199ec000, 0x19ce0000, 0x1f684000, 0x1ff5c000, 0x22d58000, 0x27651000, 0x280e5000, 0x2e2a4000, 0x2e432000, 0x2f96e000, 0x2f9c3000, 0x3343d000, 0x338bb000, 0x34032000, 0x34101000, 0x368c2000, 0x37b95000, 0x39492000, 0x39932000, 0x3b611000, 0x3c89e000, 0x40aa9000, 0x42358000, 0x4890e000, 0x495c9000, 0x4a79d000, 0x4c58e000, 0x4df9a000, 0x4f304000, 0x4fa4c000, 0x54d1d000, 0x58461000, 0x58f43000, 0x5a3d1000, 0x5a765000, 0x5c5c0000, 0x60488000, 0x60fad000, 0x613e5000, 0x61d61000, 0x62d17000, 0x641ff000, 0x67f8b000, 0x69c5d000, 0x6b931000, 0x6efd4000, 0x70333000, 0x70857000, 0x721f6000, 0x72f53000, 0x74450000, 0x746f7000, 0x76067000, 0x7774a000, 0x77ea6000, 0x80000000, }, { 28, 51, 33, 2, 30, 55, 29, 17, 40, 48, 32, 9, 39, 1, 49, 50, 37, 43, 62, 11, 10, 26, 22, 6, 8, 7, 45, 47, 46, 42, 60, 5, 12, 56, 4, 23, 35, 25, 13, 16, 61, 54, 31, 63, 34, 19, 41, 59, 38, 24, 0, 58, 53, 44, 3, 18, 52, 20, 36, 27, 14, 21, 57, 15, }, }; const pattern_t pat22 = { { 0x314d000, 0x4452000, 0x6673000, 0xab09000, 0xc80d000, 0x10eda000, 0x129c2000, 0x12f1f000, 0x13e9b000, 0x1450c000, 0x15aeb000, 0x1667c000, 0x190b2000, 0x19ac5000, 0x1c0ac000, 0x1c229000, 0x1ece8000, 0x1fc48000, 0x22abd000, 0x24268000, 0x2adce000, 0x2b809000, 0x30a11000, 0x31d08000, 0x36700000, 0x39e6a000, 0x3b84b000, 0x41e84000, 0x46301000, 0x4a326000, 0x50fda000, 0x5299a000, 0x56acf000, 0x57f66000, 0x586ab000, 0x58df5000, 0x591cc000, 0x59b91000, 0x59cbd000, 0x5b4d0000, 0x5cca7000, 0x5cfce000, 0x5d120000, 0x5d51a000, 0x5eaa0000, 0x5ebac000, 0x5f0e1000, 0x5f285000, 0x5f4d3000, 0x5ff61000, 0x60b51000, 0x61435000, 0x651fd000, 0x6b954000, 0x705aa000, 0x71a41000, 0x73ec7000, 0x75f92000, 0x76854000, 0x77cb9000, 0x782ca000, 0x7a2af000, 0x7eaa6000, 0x80000000, }, { 16, 8, 5, 59, 4, 18, 26, 43, 33, 57, 6, 47, 56, 46, 10, 54, 52, 0, 50, 30, 39, 24, 38, 63, 28, 25, 49, 31, 55, 62, 3, 17, 23, 13, 37, 53, 34, 14, 44, 12, 19, 36, 27, 61, 51, 42, 41, 60, 45, 1, 7, 35, 21, 58, 20, 15, 2, 9, 22, 29, 48, 32, 40, 11, }, }; const pattern_t pat23 = { { 0x47000, 0x680000, 0x176a000, 0x1db8000, 0x600e000, 0x808c000, 0x9e58000, 0xa82f000, 0xaebb000, 0xc938000, 0xd0eb000, 0xdc5e000, 0xe503000, 0x11e56000, 0x12dbd000, 0x14681000, 0x15200000, 0x18256000, 0x1be75000, 0x1d2a0000, 0x1ed67000, 0x27e8a000, 0x2bc39000, 0x2bf4b000, 0x2c94f000, 0x2d575000, 0x2d82e000, 0x2e440000, 0x2ecda000, 0x2fbc2000, 0x33ab0000, 0x360b8000, 0x39630000, 0x3a654000, 0x3d2b6000, 0x3eeff000, 0x41590000, 0x417ea000, 0x42ff9000, 0x4bca4000, 0x503b0000, 0x508e4000, 0x52a2e000, 0x535b6000, 0x54335000, 0x57412000, 0x57dc6000, 0x590d9000, 0x5fc0a000, 0x60552000, 0x60665000, 0x6168d000, 0x65b16000, 0x67328000, 0x6742d000, 0x68c88000, 0x6b802000, 0x6f6d2000, 0x7040e000, 0x77e31000, 0x79c71000, 0x7da4a000, 0x7e26b000, 0x80000000, }, { 63, 50, 51, 33, 28, 35, 24, 14, 4, 23, 47, 11, 37, 41, 12, 55, 62, 32, 34, 30, 25, 43, 16, 0, 3, 49, 61, 15, 57, 46, 59, 44, 31, 27, 21, 53, 5, 2, 8, 56, 52, 22, 60, 40, 20, 1, 48, 18, 17, 19, 54, 29, 9, 38, 42, 6, 39, 45, 13, 10, 26, 58, 36, 7, }, }; const pattern_t pat24 = { { 0x3890000, 0x3fd9000, 0x62d6000, 0x7df0000, 0x895c000, 0xab61000, 0xc23b000, 0x10ab3000, 0x1247c000, 0x13f00000, 0x16604000, 0x1a444000, 0x1c2c8000, 0x1c467000, 0x1d396000, 0x1e683000, 0x21080000, 0x2442a000, 0x27fea000, 0x282eb000, 0x28e2c000, 0x2a625000, 0x2b3b2000, 0x2bbd5000, 0x2c886000, 0x2cbe8000, 0x31518000, 0x35425000, 0x355f4000, 0x35d7a000, 0x3851d000, 0x396a6000, 0x3d10f000, 0x3d890000, 0x49238000, 0x4ab7e000, 0x4fadf000, 0x50603000, 0x5233a000, 0x53279000, 0x5586c000, 0x56968000, 0x58101000, 0x588b6000, 0x5bc19000, 0x5cc10000, 0x623f6000, 0x629f4000, 0x63176000, 0x63dcc000, 0x681d0000, 0x69c0e000, 0x6a9fa000, 0x6ae5e000, 0x6d2ba000, 0x6e422000, 0x73f94000, 0x77932000, 0x78b24000, 0x794c1000, 0x795d2000, 0x7ae08000, 0x7b3ce000, 0x80000000, }, { 56, 47, 54, 62, 29, 43, 25, 59, 41, 7, 52, 63, 15, 21, 16, 14, 39, 17, 45, 11, 27, 24, 55, 31, 53, 4, 6, 2, 20, 23, 5, 37, 32, 58, 13, 51, 1, 8, 3, 57, 46, 30, 35, 49, 18, 40, 9, 22, 42, 38, 34, 0, 19, 33, 26, 60, 10, 48, 36, 61, 44, 12, 50, 28, }, }; const pattern_t pat25 = { { 0xcb000, 0x22bf000, 0x2461000, 0x246b000, 0x5c6f000, 0x5fb4000, 0x69a9000, 0x718c000, 0x92e6000, 0xbb2e000, 0xd916000, 0xf3dc000, 0xf568000, 0x10246000, 0x12d53000, 0x14dfd000, 0x1598a000, 0x1956a000, 0x1b01b000, 0x1b3b8000, 0x1ce06000, 0x20bc5000, 0x21351000, 0x233b0000, 0x23f2b000, 0x24e41000, 0x29cca000, 0x2b5bd000, 0x2ba68000, 0x2bf7f000, 0x31a58000, 0x34570000, 0x39941000, 0x3b765000, 0x3cd13000, 0x3d251000, 0x3fa05000, 0x40745000, 0x45c68000, 0x4a282000, 0x4ad19000, 0x4b4aa000, 0x4ca18000, 0x4e0b8000, 0x4eb97000, 0x4f68b000, 0x4fca2000, 0x52466000, 0x52edf000, 0x5602a000, 0x57f60000, 0x5cc18000, 0x5cee3000, 0x5da37000, 0x5dba4000, 0x64b77000, 0x66e9f000, 0x68b9d000, 0x6aac9000, 0x6d873000, 0x6f7e6000, 0x71036000, 0x75a54000, 0x80000000, }, { 1, 58, 13, 5, 62, 10, 49, 48, 19, 24, 54, 57, 20, 39, 35, 41, 28, 42, 6, 44, 34, 45, 55, 3, 2, 60, 38, 36, 30, 25, 7, 23, 53, 50, 61, 29, 40, 47, 22, 12, 27, 0, 52, 31, 8, 15, 37, 11, 46, 32, 4, 56, 17, 33, 26, 43, 51, 16, 9, 59, 63, 21, 14, 18, }, }; const pattern_t pat26 = { { 0x1f4e000, 0x46f7000, 0x90a7000, 0xafe3000, 0xb2a8000, 0xb8b0000, 0xc480000, 0xc4e1000, 0xf03c000, 0xf075000, 0x14dbd000, 0x17728000, 0x1a146000, 0x1ab02000, 0x1af49000, 0x1be7a000, 0x1dc7a000, 0x1de5e000, 0x1f4f9000, 0x2092b000, 0x20a63000, 0x22937000, 0x22fe3000, 0x23e1c000, 0x28c46000, 0x294d6000, 0x2ad19000, 0x2b18b000, 0x2b233000, 0x2b685000, 0x2c792000, 0x2e6c2000, 0x2fa86000, 0x3320f000, 0x36f17000, 0x38406000, 0x38b1b000, 0x3a132000, 0x3b269000, 0x3cc43000, 0x3e2a2000, 0x3e3bb000, 0x3e83b000, 0x3ea14000, 0x4035d000, 0x4137f000, 0x4615b000, 0x50531000, 0x517c8000, 0x519e6000, 0x55ebc000, 0x594f8000, 0x5a732000, 0x5d2cb000, 0x5e409000, 0x5f394000, 0x5f3a8000, 0x60dc6000, 0x61373000, 0x6ebd6000, 0x6fd61000, 0x77161000, 0x7ce81000, 0x80000000, }, { 61, 48, 12, 55, 3, 58, 51, 56, 15, 29, 54, 11, 31, 49, 40, 37, 7, 4, 23, 35, 25, 18, 27, 43, 6, 41, 17, 45, 52, 53, 47, 16, 42, 0, 30, 13, 38, 62, 1, 8, 21, 28, 57, 9, 60, 19, 44, 50, 14, 36, 22, 2, 32, 59, 34, 10, 63, 39, 5, 24, 33, 20, 46, 26, }, }; const pattern_t pat27 = { { 0xa6a000, 0x4c7a000, 0x5183000, 0x8dda000, 0x9cbd000, 0xb860000, 0x10c24000, 0x12dda000, 0x147ab000, 0x14aa4000, 0x16c8f000, 0x17d5b000, 0x18b5c000, 0x1a163000, 0x1b0a1000, 0x24221000, 0x25ef8000, 0x267f1000, 0x268b7000, 0x26b07000, 0x273ad000, 0x27bc2000, 0x2856c000, 0x29896000, 0x2efeb000, 0x331a7000, 0x348e8000, 0x3707f000, 0x3f444000, 0x3fe2a000, 0x433b3000, 0x435d3000, 0x46d82000, 0x4a9d3000, 0x4c6cf000, 0x4ca36000, 0x4ec42000, 0x4f79c000, 0x53cd3000, 0x58c78000, 0x5d910000, 0x616cc000, 0x62800000, 0x65ded000, 0x68831000, 0x6b321000, 0x6cd46000, 0x6d0fa000, 0x6d2f9000, 0x6e353000, 0x6fd5e000, 0x706c5000, 0x7249f000, 0x75d6c000, 0x77528000, 0x783ad000, 0x79738000, 0x79bfe000, 0x79ee9000, 0x7b74a000, 0x7bb41000, 0x7bbeb000, 0x7bbfb000, 0x80000000, }, { 61, 53, 12, 15, 26, 30, 32, 2, 16, 5, 39, 43, 20, 21, 49, 37, 11, 51, 18, 44, 31, 19, 24, 40, 1, 35, 50, 6, 57, 14, 46, 17, 22, 48, 29, 7, 34, 45, 10, 63, 23, 41, 54, 38, 4, 25, 42, 13, 56, 62, 36, 28, 33, 59, 55, 3, 9, 0, 58, 60, 47, 8, 52, 27, }, }; const pattern_t pat28 = { { 0x439a000, 0x6860000, 0xd252000, 0x1105c000, 0x113c8000, 0x1429a000, 0x14922000, 0x15f32000, 0x1992f000, 0x1a1db000, 0x1a87c000, 0x1b260000, 0x1b292000, 0x1c253000, 0x1ea33000, 0x20bbc000, 0x215ae000, 0x25249000, 0x27c89000, 0x27e36000, 0x28bf2000, 0x29c27000, 0x2a575000, 0x2c6fa000, 0x31639000, 0x3184a000, 0x319c3000, 0x348a7000, 0x38aa8000, 0x39dd5000, 0x3a067000, 0x3c0dd000, 0x3cfd4000, 0x3ebb6000, 0x43259000, 0x46494000, 0x46fcb000, 0x4a050000, 0x4b5c4000, 0x4cff3000, 0x4edaa000, 0x4f025000, 0x542e1000, 0x55364000, 0x56338000, 0x56ef8000, 0x5711b000, 0x573d1000, 0x5943b000, 0x5b912000, 0x61ce2000, 0x65211000, 0x65dca000, 0x6dee2000, 0x6df30000, 0x7334d000, 0x73e76000, 0x7473a000, 0x75846000, 0x75fd0000, 0x77174000, 0x773e9000, 0x7a8db000, 0x80000000, }, { 43, 11, 8, 56, 5, 22, 42, 55, 14, 32, 2, 47, 24, 51, 35, 25, 15, 58, 41, 27, 33, 37, 4, 36, 7, 53, 26, 48, 38, 19, 29, 28, 40, 10, 1, 46, 59, 63, 61, 62, 60, 30, 21, 39, 44, 57, 20, 18, 17, 54, 49, 52, 3, 12, 45, 13, 50, 9, 16, 23, 0, 6, 31, 34, }, }; const pattern_t pat29 = { { 0x363000, 0x9bc000, 0x1907000, 0x41d5000, 0x5a6e000, 0x9f36000, 0xa3ee000, 0x14b98000, 0x1845c000, 0x188ea000, 0x1b297000, 0x1c024000, 0x1e1eb000, 0x1f3a4000, 0x2047f000, 0x2420a000, 0x28871000, 0x296dd000, 0x2c92c000, 0x2dd42000, 0x3444f000, 0x35b90000, 0x3683c000, 0x3d8ea000, 0x3fe6b000, 0x4200e000, 0x421cf000, 0x42a46000, 0x44463000, 0x44e61000, 0x45c82000, 0x485f8000, 0x48fe8000, 0x4a532000, 0x4a6fd000, 0x4c8f9000, 0x4dbd7000, 0x5052a000, 0x512bb000, 0x5281d000, 0x5315d000, 0x5a202000, 0x5a9fc000, 0x5c11a000, 0x6010b000, 0x62aa3000, 0x63d05000, 0x6774c000, 0x6776d000, 0x68105000, 0x699d5000, 0x69bc2000, 0x6b1b9000, 0x704d5000, 0x73d5c000, 0x73d94000, 0x78483000, 0x78c8c000, 0x78cc5000, 0x7ac8d000, 0x7ae00000, 0x7b597000, 0x7e6ab000, 0x80000000, }, { 52, 40, 59, 29, 42, 34, 63, 44, 33, 37, 51, 23, 5, 36, 38, 43, 9, 4, 28, 55, 1, 6, 21, 26, 13, 24, 30, 15, 35, 17, 46, 20, 16, 10, 49, 48, 39, 62, 19, 14, 61, 27, 53, 2, 57, 58, 45, 7, 56, 50, 54, 25, 31, 11, 22, 47, 3, 0, 32, 12, 8, 41, 60, 18, }, }; const pattern_t pat30 = { { 0x45c5000, 0x6bf3000, 0xc293000, 0xe470000, 0xe5b7000, 0x1256c000, 0x1444d000, 0x15699000, 0x16e86000, 0x1a4d5000, 0x1b803000, 0x1dcf9000, 0x1dd6f000, 0x1f57f000, 0x22879000, 0x263e9000, 0x29423000, 0x2a1a9000, 0x2a699000, 0x2c8fb000, 0x2d2e0000, 0x2ec5e000, 0x317a4000, 0x35a64000, 0x36967000, 0x37299000, 0x37c07000, 0x3b9bb000, 0x3c054000, 0x3ccbc000, 0x3d94a000, 0x3e2e9000, 0x3e7a4000, 0x40b98000, 0x44658000, 0x44738000, 0x44fe3000, 0x451d9000, 0x4536c000, 0x46df2000, 0x48855000, 0x503ce000, 0x53104000, 0x531fc000, 0x54c1b000, 0x56086000, 0x5642b000, 0x573a4000, 0x5887f000, 0x5a871000, 0x5c970000, 0x5e566000, 0x62b8f000, 0x642ce000, 0x65ee5000, 0x66db3000, 0x6727c000, 0x6a9a2000, 0x74a8f000, 0x7c29a000, 0x7cc57000, 0x7f221000, 0x7f28f000, 0x80000000, }, { 29, 35, 8, 49, 30, 55, 27, 38, 58, 61, 0, 28, 15, 39, 5, 37, 32, 42, 46, 54, 12, 14, 1, 31, 59, 11, 47, 9, 13, 50, 2, 62, 60, 18, 20, 51, 23, 24, 53, 6, 25, 48, 41, 3, 33, 57, 44, 19, 22, 52, 4, 45, 10, 21, 56, 36, 17, 43, 7, 63, 16, 34, 26, 40, }, }; const pattern_t pat31 = { { 0x143f000, 0x2068000, 0x328c000, 0x70a6000, 0x92a7000, 0x93dd000, 0xa3a8000, 0xbe51000, 0xbfc8000, 0xe353000, 0x1272f000, 0x143a4000, 0x16825000, 0x20bf8000, 0x20d9f000, 0x21e32000, 0x22426000, 0x2246b000, 0x22cea000, 0x25dc2000, 0x29324000, 0x29cd1000, 0x2aa44000, 0x2cd84000, 0x2dafb000, 0x2e74b000, 0x2f5b1000, 0x3a7a9000, 0x3bb38000, 0x3c11a000, 0x3c30a000, 0x3e2f1000, 0x4187b000, 0x42190000, 0x44e34000, 0x4d850000, 0x53ceb000, 0x540db000, 0x54937000, 0x5530a000, 0x5a111000, 0x5c280000, 0x5ef17000, 0x5fccf000, 0x64434000, 0x6498e000, 0x662c4000, 0x6a7e2000, 0x6b5a1000, 0x6c11f000, 0x6dd97000, 0x6ef1b000, 0x6f44e000, 0x7084f000, 0x73b53000, 0x7872c000, 0x78ed7000, 0x7935b000, 0x79bf9000, 0x7a6af000, 0x7b6fd000, 0x7bd42000, 0x7f233000, 0x80000000, }, { 6, 25, 28, 44, 27, 43, 58, 33, 23, 21, 16, 48, 30, 26, 5, 20, 49, 38, 2, 45, 11, 61, 17, 0, 53, 13, 7, 52, 40, 31, 36, 4, 10, 8, 24, 22, 42, 63, 35, 60, 47, 29, 46, 19, 1, 3, 34, 55, 59, 14, 39, 12, 32, 50, 62, 54, 56, 51, 57, 15, 41, 18, 37, 9, }, }; const pattern_t* patterns[] = {&trivial_pattern, &pat0, &pat1, &pat2, &pat3, &pat4, &pat5, &pat6, &pat7, &pat8, &pat9, &pat10, &pat11, &pat12, &pat13, &pat14, &pat15, &pat16, &pat17, &pat18, &pat19, &pat20, &pat21, &pat22, &pat23, &pat24, &pat25, &pat26, &pat27, &pat28, &pat29, &pat30, &pat31}; //static variables used by the worker threads static int outfd = 0; static sem_t chunk_sems[NUM_THREADS - 1][NUM_CHUNKS]; static void usage() { (void) fprintf(stderr, "usage: fsync_integrity \n"); exit(2); } /* Fills a buffer with a special marker. The marker contains information about * the file offset where this buffer is supposed to go, and whether it will * be written by a leader or a follower */ static void marker_fill(uint64_t* buf, int file_ofs, size_t len, int thread_num){ int ofs; uint32_t thread_mark = thread_num; uint32_t final_mark = 0xe005b0ca; //"CABOOSE" in little endian for (ofs = file_ofs; ofs < file_ofs + len; ofs += sizeof(uint64_t)){ uint64_t mark = ((thread_num == (NUM_THREADS - 1) ? (uint64_t)final_mark : (uint64_t)thread_mark) << (uint64_t)32) | htonl(ofs & 0xFFFFFFFF); int buf_idx = (ofs - file_ofs) / sizeof(uint64_t); buf[buf_idx] = mark; } } static int verify_file(int fd, const pattern_t* p_pat){ int chunk_idx; int good_data = 1; int err = 0; for(chunk_idx=0; chunk_idx < NUM_CHUNKS; chunk_idx++){ int i; uint32_t chunk_start, chunk_end; get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end); size_t size = chunk_end - chunk_start; uint64_t* desired_buf = malloc(size); uint64_t* actual_buf = malloc(size); marker_fill(desired_buf, chunk_start, size, NUM_THREADS - 1); //read the actual data from the file if( read(fd, actual_buf, size) <= 0 ){ perror("read"); exit(1); } //verify the data for(i=0; i < size / sizeof(uint64_t); i++){ int chunk_offset = sizeof(uint64_t) * i; int file_offset = chunk_start + chunk_offset; if (good_data && (actual_buf[i] != desired_buf[i])){ fprintf(stderr, "fsync_integrity: miscompare at " "chunk %i, chunk offset %x, file offset %x\n", chunk_idx, chunk_offset, file_offset); fprintf(stderr, "Expected %016lx, got %016lx\n", desired_buf[i], actual_buf[i]); err = 1; good_data = 0; } else if (!good_data && (actual_buf[i] == desired_buf[i])) { fprintf(stderr, "fsync_integrity: miscompare ends at " "chunk %i, chunk offset %x, file offset %x\n", chunk_idx, chunk_offset, file_offset); good_data = 1; } } free(desired_buf); free(actual_buf); } return (err); } /* Writes a special marker to every byte within the chunk */ static void -write_chunk(pattern_t* p_pat, int chunk_idx, int thread_num) +write_chunk(const pattern_t* p_pat, int chunk_idx, int thread_num) { uint32_t chunk_start, chunk_end; get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end); size_t size = chunk_end - chunk_start; uint64_t* buf = malloc(size); marker_fill(buf, chunk_start, size, thread_num); pwrite(outfd, (void*)buf, size, chunk_start); free(buf); } static void my_sync(int fd){ if (fsync(fd)){ perror("fsync"); exit(1); } } static void* worker(void* args) { int perm_idx, thread_num; thread_data_t* data; data = (thread_data_t*)args; thread_num = data->thread_num; for(perm_idx = 0; perm_idx < NUM_CHUNKS; perm_idx++) { int chunk_idx = data->pat->permutation[perm_idx]; /* Acquire the semaphore, if necessary */ if (thread_num > 0) { if (-1 == sem_wait(&chunk_sems[thread_num - 1][chunk_idx])){ perror("sem_wait"); exit(1); } } /* Write the data */ write_chunk(data->pat, chunk_idx, thread_num); /* Sync, if we are an even thread */ if ((thread_num % 2) == 0) my_sync(outfd); /* Post the final semaphore, if necessary */ if (thread_num < NUM_THREADS - 1) { if (sem_post(&chunk_sems[thread_num][chunk_idx]) == -1){ perror("sem_post"); exit(1); } } } return 0; } int main(int argc, char** argv) { int rep; int pat; pthread_t threads[NUM_THREADS]; thread_data_t thread_data[NUM_THREADS]; if (argc != 2){ usage(); } for(rep=0; rep < NUM_REPETITIONS; rep++){ printf("Starting repetition %d\n", rep); for(pat=0; pat < sizeof(patterns) / sizeof(patterns[0]); pat++){ int i; const pattern_t *pat_p = patterns[pat]; /* pattern_t *pat_p = (void *)(uintptr_t)(const void *)patterns[pat];*/ int sem_idx; int ofs=0; /* printf("Starting on patterns[%d]\n" , pat);*/ outfd = open(argv[1], O_RDWR | O_CREAT | O_TRUNC, 0644); if (outfd == -1){ perror("open"); exit(1); } //set the file size if ( ftruncate(outfd, FSIZE)){ perror("ftruncate"); exit(1); } //Zero-fill the file to avoid fragmentation, as recommended by mmap(2). for(ofs=0; ofs < FSIZE; ofs+=CLUSTERSIZE){ char buffer[CLUSTERSIZE]; bzero(buffer, CLUSTERSIZE); if ( -1 == write(outfd, buffer, CLUSTERSIZE)){ perror("write"); exit(1); } } //Return the file pointer to the beginning prior to mmap if (-1 == lseek(outfd, 0, SEEK_SET)){ perror("lseek"); } //Create the semaphores for(i=0; i < NUM_THREADS - 1; i++) { for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){ if (sem_init(&chunk_sems[i][sem_idx], 0, 0)){ perror("sem_init"); exit(1); } } } //Create the worker threads for(i=0; i < NUM_THREADS; i++) { thread_data[i].pat = pat_p; thread_data[i].thread_num = i; if (pthread_create(&threads[i], NULL, worker, (void*)&thread_data[i])){ perror("pthread_create"); exit(1); } } //Join the threads for(i=0; i < NUM_THREADS; i++) { if (pthread_join(threads[i], NULL)){ perror("pthread_join"); exit(1); } } //destroy the semaphores for(i=0; i < NUM_THREADS - 1; i++) { for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){ if (sem_destroy(&chunk_sems[i][sem_idx])){ perror("sem_destory"); exit(1); } } } //printf("destroyed semaphores\n"); //Verify the contents of the file. if (verify_file(outfd, patterns[pat])) { exit(1); } //printf("finished verify_file\n"); //close the file: if (close(outfd)){ perror("close"); exit(1); } } } return 0; }