1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 2013 Spectra Logic. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /*
28 * Verify the integrity of non-aligned writes to the same blocks within the same
29 * transaction group, where an fsync is issued by a non-final writer.
30 *
31 * This test verifies that the unoverride in the following sequence of events is
32 * handled correctly:
33 *
34 * 1) A new transaction group opens
35 * 2) A write is issued to a certain block
36 * 3) The writer fsyncs() that file
37 * 4) TBD module immediately writes that block, then places an override in the
38 * syncer's TBD data structure, indicating that it doesn't need to write that
39 * block when syncing.
40 * 5) Another write is issued to the same block, with different data.
41 * 6) TBD module unoverrides that block in the syncer's TBD data structure
42 * 7) The syncer writes that block
43 *
44 * Outline:
45 * Create a big zero-filled file.
46 * Create a bunch of different IO patterns. Each IO pattern consists of:
47 * * A partition of the file range into 64 different non-overlapping chunks.
48 * * A permutation of those chunks
49 * For each repetition:
50 * For each IO pattern:
51 * Create one binary semaphore per chunk, per (n-1) threads
52 * Create n threads.
53 * The first thread will write each chunk in order. It will post a
54 * semaphore after each write to indicate that it has completed
55 * writing that chunk.
56 * The second thread will pend on those semaphores in order. Each time it
57 * receives a semaphore, it will write a different pattern to that
58 * chunk. Then it will post a different semaphore to signal the next
59 * thread.
60 * The final thread will not post any semaphores
61 * Every even-numbered thread, starting with the first (0th), will fsync()
62 * the file after its write. The final thread, being odd-numbered,
63 * won't.
64 * Join all threads
65 * Read the entire file and verify that
66 * 1) Every write went to the correct location
67 * 2) The final thread's write is left in the file
68 */
69
70 #include <stdint.h>
71 #include <sys/types.h>
72 #include <sys/uio.h>
73 #include <unistd.h>
74 #include <sys/stat.h>
75 #include <fcntl.h>
76 #include <stdio.h>
77 #include <errno.h>
78 #include <semaphore.h>
79 #include <pthread.h>
80 #include <stdlib.h>
81 #include <strings.h>
82 #include <string.h>
83 #include <sys/mman.h>
84 #include <assert.h>
85 #include <arpa/inet.h>
86
87 #define NUM_REPETITIONS 16
88 #define CLUSTERSIZE (1 << 17)
89 #define NUM_CHUNKS 64
90 #define FSIZE (64 * (CLUSTERSIZE)) //FSIZE may range from NUM_CHUNKS clusters to 8GB
91 #define USE_THREADS 1
92 #define NUM_THREADS 8
93
94 typedef struct {
95 //partitions describes the boundaries between chunks. Each element is a
96 //fraction of the filesize in 1.31 fixed point format. So the boundary
97 //between chunk n and chunk n-1 is (FSIZE * partitions[n-1] / (1<<31) .
98 //partitions[-1] is understood to be 0 and partitions[NUM_CHUNKS] must be 1.0
99 //partitions is sorted, of course.
100 //Partition boundaries must be dword aligned. Thus, in order to work with
101 //multiple values of FSIZE, partitions values must be aligned to multiples of
102 //8 / (NUM_CHUNKS * CLUSTERSIZE) = 1 / 524288 = 0x0.00002
103 uint32_t partitions[NUM_CHUNKS];
104 int permutation[NUM_CHUNKS]; //the order in which to write the chunks
105 } pattern_t;
106
107 typedef struct {
108 int thread_num;
109 const pattern_t* pat;
110 } thread_data_t;
111
112
113 /* Returns (via begin and end) the range of a chunk. Begin is inclusive,
114 * end is exclusive */
get_chunk_range(const pattern_t * pat,int chunk,uint32_t * begin,uint32_t * end)115 void get_chunk_range(const pattern_t* pat, int chunk, uint32_t* begin, uint32_t* end){
116 if (chunk == 0){
117 *begin = 0;
118 }
119 else{
120 *begin = (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk - 1] >> 31);
121 }
122 *end = (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk] >> 31);
123 }
124
125
126 /* The most basic, trivial IO pattern. Fully sequential, and the follower
127 * writes every other block */
128 const pattern_t trivial_pattern = {
129 {0x2000000, 0x4000000, 0x6000000, 0x8000000, 0xa000000, 0xc000000, 0xe000000, 0x10000000,
130 0x12000000, 0x14000000, 0x16000000, 0x18000000, 0x1a000000, 0x1c000000, 0x1e000000, 0x20000000,
131 0x22000000, 0x24000000, 0x26000000, 0x28000000, 0x2a000000, 0x2c000000, 0x2e000000, 0x30000000,
132 0x32000000, 0x34000000, 0x36000000, 0x38000000, 0x3a000000, 0x3c000000, 0x3e000000, 0x40000000,
133 0x42000000, 0x44000000, 0x46000000, 0x48000000, 0x4a000000, 0x4c000000, 0x4e000000, 0x50000000,
134 0x52000000, 0x54000000, 0x56000000, 0x58000000, 0x5a000000, 0x5c000000, 0x5e000000, 0x60000000,
135 0x62000000, 0x64000000, 0x66000000, 0x68000000, 0x6a000000, 0x6c000000, 0x6e000000, 0x70000000,
136 0x72000000, 0x74000000, 0x76000000, 0x78000000, 0x7a000000, 0x7c000000, 0x7e000000, 0x80000000},
137 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
138 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
139 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
140 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63},
141 };
142
143 //The below patterns were randomly generated
144 const pattern_t pat0 = {
145 { 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, },
146 { 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, },
147 };
148 const pattern_t pat1 = {
149 { 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, },
150 { 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, },
151 };
152 const pattern_t pat2 = {
153 { 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, },
154 { 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, },
155 };
156 const pattern_t pat3 = {
157 { 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, },
158 { 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, },
159 };
160 const pattern_t pat4 = {
161 { 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, },
162 { 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, },
163 };
164 const pattern_t pat5 = {
165 { 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, },
166 { 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, },
167 };
168 const pattern_t pat6 = {
169 { 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, },
170 { 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, },
171 };
172 const pattern_t pat7 = {
173 { 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, },
174 { 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, },
175 };
176 const pattern_t pat8 = {
177 { 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, },
178 { 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, },
179 };
180 const pattern_t pat9 = {
181 { 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, },
182 { 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, },
183 };
184 const pattern_t pat10 = {
185 { 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, },
186 { 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, },
187 };
188 const pattern_t pat11 = {
189 { 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, },
190 { 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, },
191 };
192 const pattern_t pat12 = {
193 { 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, },
194 { 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, },
195 };
196 const pattern_t pat13 = {
197 { 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, },
198 { 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, },
199 };
200 const pattern_t pat14 = {
201 { 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, },
202 { 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, },
203 };
204 const pattern_t pat15 = {
205 { 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, },
206 { 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, },
207 };
208 const pattern_t pat16 = {
209 { 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, },
210 { 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, },
211 };
212 const pattern_t pat17 = {
213 { 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, },
214 { 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, },
215 };
216 const pattern_t pat18 = {
217 { 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, },
218 { 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, },
219 };
220 const pattern_t pat19 = {
221 { 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, },
222 { 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, },
223 };
224 const pattern_t pat20 = {
225 { 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, },
226 { 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, },
227 };
228 const pattern_t pat21 = {
229 { 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, },
230 { 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, },
231 };
232 const pattern_t pat22 = {
233 { 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, },
234 { 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, },
235 };
236 const pattern_t pat23 = {
237 { 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, },
238 { 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, },
239 };
240 const pattern_t pat24 = {
241 { 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, },
242 { 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, },
243 };
244 const pattern_t pat25 = {
245 { 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, },
246 { 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, },
247 };
248 const pattern_t pat26 = {
249 { 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, },
250 { 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, },
251 };
252 const pattern_t pat27 = {
253 { 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, },
254 { 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, },
255 };
256 const pattern_t pat28 = {
257 { 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, },
258 { 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, },
259 };
260 const pattern_t pat29 = {
261 { 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, },
262 { 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, },
263 };
264 const pattern_t pat30 = {
265 { 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, },
266 { 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, },
267 };
268 const pattern_t pat31 = {
269 { 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, },
270 { 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, },
271 };
272 const pattern_t* patterns[] = {&trivial_pattern,
273 &pat0, &pat1, &pat2, &pat3, &pat4, &pat5, &pat6, &pat7,
274 &pat8, &pat9, &pat10, &pat11, &pat12, &pat13, &pat14, &pat15,
275 &pat16, &pat17, &pat18, &pat19, &pat20, &pat21, &pat22, &pat23,
276 &pat24, &pat25, &pat26, &pat27, &pat28, &pat29, &pat30, &pat31};
277
278 //static variables used by the worker threads
279 static int outfd = 0;
280 static sem_t chunk_sems[NUM_THREADS - 1][NUM_CHUNKS];
281
282 static void
usage()283 usage()
284 {
285 (void) fprintf(stderr, "usage: fsync_integrity <file name>\n");
286 exit(2);
287 }
288
289
290 /* Fills a buffer with a special marker. The marker contains information about
291 * the file offset where this buffer is supposed to go, and whether it will
292 * be written by a leader or a follower */
293 static void
marker_fill(uint64_t * buf,int file_ofs,size_t len,int thread_num)294 marker_fill(uint64_t* buf, int file_ofs, size_t len, int thread_num){
295 int ofs;
296 uint32_t thread_mark = thread_num;
297 uint32_t final_mark = 0xe005b0ca; //"CABOOSE" in little endian
298 for (ofs = file_ofs; ofs < file_ofs + len; ofs += sizeof(uint64_t)){
299 uint64_t mark = ((thread_num == (NUM_THREADS - 1) ?
300 (uint64_t)final_mark : (uint64_t)thread_mark) << (uint64_t)32) |
301 htonl(ofs & 0xFFFFFFFF);
302 int buf_idx = (ofs - file_ofs) / sizeof(uint64_t);
303 buf[buf_idx] = mark;
304 }
305 }
306
307 static int
verify_file(int fd,const pattern_t * p_pat)308 verify_file(int fd, const pattern_t* p_pat){
309 int chunk_idx;
310 int good_data = 1;
311 int err = 0;
312
313 for(chunk_idx=0; chunk_idx < NUM_CHUNKS; chunk_idx++){
314 int i;
315 uint32_t chunk_start, chunk_end;
316 get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end);
317 size_t size = chunk_end - chunk_start;
318 uint64_t* desired_buf = malloc(size);
319 uint64_t* actual_buf = malloc(size);
320 marker_fill(desired_buf, chunk_start, size, NUM_THREADS - 1);
321
322 //read the actual data from the file
323 if( read(fd, actual_buf, size) <= 0 ){
324 perror("read");
325 exit(1);
326 }
327
328 //verify the data
329 for(i=0; i < size / sizeof(uint64_t); i++){
330 int chunk_offset = sizeof(uint64_t) * i;
331 int file_offset = chunk_start + chunk_offset;
332 if (good_data && (actual_buf[i] != desired_buf[i])){
333 fprintf(stderr, "fsync_integrity: miscompare at "
334 "chunk %i, chunk offset %x, file offset %x\n",
335 chunk_idx, chunk_offset, file_offset);
336 fprintf(stderr, "Expected %016lx, got %016lx\n",
337 desired_buf[i], actual_buf[i]);
338 err = 1;
339 good_data = 0;
340 }
341 else if (!good_data && (actual_buf[i] == desired_buf[i])) {
342 fprintf(stderr, "fsync_integrity: miscompare ends at "
343 "chunk %i, chunk offset %x, file offset %x\n",
344 chunk_idx, chunk_offset, file_offset);
345 good_data = 1;
346 }
347 }
348 free(desired_buf);
349 free(actual_buf);
350 }
351
352 return (err);
353 }
354
355 /* Writes a special marker to every byte within the chunk */
356 static void
write_chunk(const pattern_t * p_pat,int chunk_idx,int thread_num)357 write_chunk(const pattern_t* p_pat, int chunk_idx, int thread_num)
358 {
359 uint32_t chunk_start, chunk_end;
360 get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end);
361 size_t size = chunk_end - chunk_start;
362 uint64_t* buf = malloc(size);
363 marker_fill(buf, chunk_start, size, thread_num);
364 pwrite(outfd, (void*)buf, size, chunk_start);
365 free(buf);
366 }
367
368 static void
my_sync(int fd)369 my_sync(int fd){
370 if (fsync(fd)){
371 perror("fsync");
372 exit(1);
373 }
374 }
375
376
377 static void*
worker(void * args)378 worker(void* args)
379 {
380 int perm_idx, thread_num;
381 thread_data_t* data;
382
383 data = (thread_data_t*)args;
384 thread_num = data->thread_num;
385
386 for(perm_idx = 0; perm_idx < NUM_CHUNKS; perm_idx++)
387 {
388 int chunk_idx = data->pat->permutation[perm_idx];
389 /* Acquire the semaphore, if necessary */
390 if (thread_num > 0) {
391 if (-1 == sem_wait(&chunk_sems[thread_num - 1][chunk_idx])){
392 perror("sem_wait");
393 exit(1);
394 }
395 }
396 /* Write the data */
397 write_chunk(data->pat, chunk_idx, thread_num);
398 /* Sync, if we are an even thread */
399 if ((thread_num % 2) == 0)
400 my_sync(outfd);
401 /* Post the final semaphore, if necessary */
402 if (thread_num < NUM_THREADS - 1) {
403 if (sem_post(&chunk_sems[thread_num][chunk_idx]) == -1){
404 perror("sem_post");
405 exit(1);
406 }
407 }
408 }
409 return 0;
410 }
411
412
413 int
main(int argc,char ** argv)414 main(int argc, char** argv)
415 {
416 int rep;
417 int pat;
418 pthread_t threads[NUM_THREADS];
419 thread_data_t thread_data[NUM_THREADS];
420
421 if (argc != 2){
422 usage();
423 }
424
425 for(rep=0; rep < NUM_REPETITIONS; rep++){
426 printf("Starting repetition %d\n", rep);
427 for(pat=0; pat < sizeof(patterns) / sizeof(patterns[0]); pat++){
428 int i;
429 const pattern_t *pat_p = patterns[pat];
430 /* pattern_t *pat_p = (void *)(uintptr_t)(const void *)patterns[pat];*/
431 int sem_idx;
432 int ofs=0;
433
434 /* printf("Starting on patterns[%d]\n" , pat);*/
435 outfd = open(argv[1], O_RDWR | O_CREAT | O_TRUNC, 0644);
436 if (outfd == -1){
437 perror("open");
438 exit(1);
439 }
440
441 //set the file size
442 if ( ftruncate(outfd, FSIZE)){
443 perror("ftruncate");
444 exit(1);
445 }
446
447 //Zero-fill the file to avoid fragmentation, as recommended by mmap(2).
448 for(ofs=0; ofs < FSIZE; ofs+=CLUSTERSIZE){
449 char buffer[CLUSTERSIZE];
450 bzero(buffer, CLUSTERSIZE);
451 if ( -1 == write(outfd, buffer, CLUSTERSIZE)){
452 perror("write");
453 exit(1);
454 }
455 }
456 //Return the file pointer to the beginning prior to mmap
457 if (-1 == lseek(outfd, 0, SEEK_SET)){
458 perror("lseek");
459 }
460
461 //Create the semaphores
462 for(i=0; i < NUM_THREADS - 1; i++) {
463 for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){
464 if (sem_init(&chunk_sems[i][sem_idx], 0, 0)){
465 perror("sem_init");
466 exit(1);
467 }
468 }
469 }
470
471 //Create the worker threads
472 for(i=0; i < NUM_THREADS; i++) {
473 thread_data[i].pat = pat_p;
474 thread_data[i].thread_num = i;
475 if (pthread_create(&threads[i], NULL, worker, (void*)&thread_data[i])){
476 perror("pthread_create");
477 exit(1);
478 }
479 }
480
481 //Join the threads
482 for(i=0; i < NUM_THREADS; i++) {
483 if (pthread_join(threads[i], NULL)){
484 perror("pthread_join");
485 exit(1);
486 }
487 }
488
489 //destroy the semaphores
490 for(i=0; i < NUM_THREADS - 1; i++) {
491 for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){
492 if (sem_destroy(&chunk_sems[i][sem_idx])){
493 perror("sem_destory");
494 exit(1);
495 }
496 }
497 }
498 //printf("destroyed semaphores\n");
499
500
501 //Verify the contents of the file.
502 if (verify_file(outfd, patterns[pat])) {
503 exit(1);
504 }
505 //printf("finished verify_file\n");
506
507 //close the file:
508 if (close(outfd)){
509 perror("close");
510 exit(1);
511 }
512 }
513 }
514
515 return 0;
516 }
517