aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/842/842.h127
-rw-r--r--lib/842/842_compress.c626
-rw-r--r--lib/842/842_debugfs.h52
-rw-r--r--lib/842/842_decompress.c405
-rw-r--r--lib/842/Makefile2
-rw-r--r--lib/Kconfig6
-rw-r--r--lib/Kconfig.debug66
-rw-r--r--lib/Makefile2
-rw-r--r--lib/cpu_rmap.c2
-rw-r--r--lib/cpumask.c9
-rw-r--r--lib/mpi/longlong.h4
-rw-r--r--lib/mpi/mpicoder.c87
-rw-r--r--lib/mpi/mpiutil.c6
-rw-r--r--lib/radix-tree.c2
-rw-r--r--lib/raid6/x86.h2
-rw-r--r--lib/rhashtable.c1
-rw-r--r--lib/scatterlist.c32
-rw-r--r--lib/strnlen_user.c18
-rw-r--r--lib/swiotlb.c16
-rw-r--r--lib/timerqueue.c10
20 files changed, 1430 insertions, 45 deletions
diff --git a/lib/842/842.h b/lib/842/842.h
new file mode 100644
index 000000000000..7c200030acf7
--- /dev/null
+++ b/lib/842/842.h
@@ -0,0 +1,127 @@
1
2#ifndef __842_H__
3#define __842_H__
4
5/* The 842 compressed format is made up of multiple blocks, each of
6 * which have the format:
7 *
8 * <template>[arg1][arg2][arg3][arg4]
9 *
10 * where there are between 0 and 4 template args, depending on the specific
11 * template operation. For normal operations, each arg is either a specific
12 * number of data bytes to add to the output buffer, or an index pointing
13 * to a previously-written number of data bytes to copy to the output buffer.
14 *
15 * The template code is a 5-bit value. This code indicates what to do with
16 * the following data. Template codes from 0 to 0x19 should use the template
17 * table, the static "decomp_ops" table used in decompress. For each template
18 * (table row), there are between 1 and 4 actions; each action corresponds to
19 * an arg following the template code bits. Each action is either a "data"
20 * type action, or a "index" type action, and each action results in 2, 4, or 8
21 * bytes being written to the output buffer. Each template (i.e. all actions
22 * in the table row) will add up to 8 bytes being written to the output buffer.
23 * Any row with less than 4 actions is padded with noop actions, indicated by
24 * N0 (for which there is no corresponding arg in the compressed data buffer).
25 *
26 * "Data" actions, indicated in the table by D2, D4, and D8, mean that the
27 * corresponding arg is 2, 4, or 8 bytes, respectively, in the compressed data
28 * buffer should be copied directly to the output buffer.
29 *
30 * "Index" actions, indicated in the table by I2, I4, and I8, mean the
31 * corresponding arg is an index parameter that points to, respectively, a 2,
32 * 4, or 8 byte value already in the output buffer, that should be copied to
33 * the end of the output buffer. Essentially, the index points to a position
34 * in a ring buffer that contains the last N bytes of output buffer data.
35 * The number of bits for each index's arg are: 8 bits for I2, 9 bits for I4,
36 * and 8 bits for I8. Since each index points to a 2, 4, or 8 byte section,
37 * this means that I2 can reference 512 bytes ((2^8 bits = 256) * 2 bytes), I4
38 * can reference 2048 bytes ((2^9 = 512) * 4 bytes), and I8 can reference 2048
39 * bytes ((2^8 = 256) * 8 bytes). Think of it as a kind-of ring buffer for
40 * each of I2, I4, and I8 that are updated for each byte written to the output
41 * buffer. In this implementation, the output buffer is directly used for each
42 * index; there is no additional memory required. Note that the index is into
43 * a ring buffer, not a sliding window; for example, if there have been 260
44 * bytes written to the output buffer, an I2 index of 0 would index to byte 256
45 * in the output buffer, while an I2 index of 16 would index to byte 16 in the
46 * output buffer.
47 *
48 * There are also 3 special template codes; 0x1b for "repeat", 0x1c for
49 * "zeros", and 0x1e for "end". The "repeat" operation is followed by a 6 bit
50 * arg N indicating how many times to repeat. The last 8 bytes written to the
51 * output buffer are written again to the output buffer, N + 1 times. The
52 * "zeros" operation, which has no arg bits, writes 8 zeros to the output
53 * buffer. The "end" operation, which also has no arg bits, signals the end
54 * of the compressed data. There may be some number of padding (don't care,
55 * but usually 0) bits after the "end" operation bits, to fill the buffer
56 * length to a specific byte multiple (usually a multiple of 8, 16, or 32
57 * bytes).
58 *
59 * This software implementation also uses one of the undefined template values,
60 * 0x1d as a special "short data" template code, to represent less than 8 bytes
61 * of uncompressed data. It is followed by a 3 bit arg N indicating how many
62 * data bytes will follow, and then N bytes of data, which should be copied to
63 * the output buffer. This allows the software 842 compressor to accept input
64 * buffers that are not an exact multiple of 8 bytes long. However, those
65 * compressed buffers containing this sw-only template will be rejected by
66 * the 842 hardware decompressor, and must be decompressed with this software
67 * library. The 842 software compression module includes a parameter to
68 * disable using this sw-only "short data" template, and instead simply
69 * reject any input buffer that is not a multiple of 8 bytes long.
70 *
71 * After all actions for each operation code are processed, another template
72 * code is in the next 5 bits. The decompression ends once the "end" template
73 * code is detected.
74 */
75
76#include <linux/module.h>
77#include <linux/kernel.h>
78#include <linux/bitops.h>
79#include <asm/unaligned.h>
80
81#include <linux/sw842.h>
82
83/* special templates */
84#define OP_REPEAT (0x1B)
85#define OP_ZEROS (0x1C)
86#define OP_END (0x1E)
87
88/* sw only template - this is not in the hw design; it's used only by this
89 * software compressor and decompressor, to allow input buffers that aren't
90 * a multiple of 8.
91 */
92#define OP_SHORT_DATA (0x1D)
93
94/* additional bits of each op param */
95#define OP_BITS (5)
96#define REPEAT_BITS (6)
97#define SHORT_DATA_BITS (3)
98#define I2_BITS (8)
99#define I4_BITS (9)
100#define I8_BITS (8)
101
102#define REPEAT_BITS_MAX (0x3f)
103#define SHORT_DATA_BITS_MAX (0x7)
104
105/* Arbitrary values used to indicate action */
106#define OP_ACTION (0x70)
107#define OP_ACTION_INDEX (0x10)
108#define OP_ACTION_DATA (0x20)
109#define OP_ACTION_NOOP (0x40)
110#define OP_AMOUNT (0x0f)
111#define OP_AMOUNT_0 (0x00)
112#define OP_AMOUNT_2 (0x02)
113#define OP_AMOUNT_4 (0x04)
114#define OP_AMOUNT_8 (0x08)
115
116#define D2 (OP_ACTION_DATA | OP_AMOUNT_2)
117#define D4 (OP_ACTION_DATA | OP_AMOUNT_4)
118#define D8 (OP_ACTION_DATA | OP_AMOUNT_8)
119#define I2 (OP_ACTION_INDEX | OP_AMOUNT_2)
120#define I4 (OP_ACTION_INDEX | OP_AMOUNT_4)
121#define I8 (OP_ACTION_INDEX | OP_AMOUNT_8)
122#define N0 (OP_ACTION_NOOP | OP_AMOUNT_0)
123
124/* the max of the regular templates - not including the special templates */
125#define OPS_MAX (0x1a)
126
127#endif
diff --git a/lib/842/842_compress.c b/lib/842/842_compress.c
new file mode 100644
index 000000000000..7ce68948e68c
--- /dev/null
+++ b/lib/842/842_compress.c
@@ -0,0 +1,626 @@
1/*
2 * 842 Software Compression
3 *
4 * Copyright (C) 2015 Dan Streetman, IBM Corp
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * See 842.h for details of the 842 compressed format.
17 */
18
19#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
20#define MODULE_NAME "842_compress"
21
22#include <linux/hashtable.h>
23
24#include "842.h"
25#include "842_debugfs.h"
26
27#define SW842_HASHTABLE8_BITS (10)
28#define SW842_HASHTABLE4_BITS (11)
29#define SW842_HASHTABLE2_BITS (10)
30
31/* By default, we allow compressing input buffers of any length, but we must
32 * use the non-standard "short data" template so the decompressor can correctly
33 * reproduce the uncompressed data buffer at the right length. However the
34 * hardware 842 compressor will not recognize the "short data" template, and
35 * will fail to decompress any compressed buffer containing it (I have no idea
36 * why anyone would want to use software to compress and hardware to decompress
37 * but that's beside the point). This parameter forces the compression
38 * function to simply reject any input buffer that isn't a multiple of 8 bytes
39 * long, instead of using the "short data" template, so that all compressed
40 * buffers produced by this function will be decompressable by the 842 hardware
41 * decompressor. Unless you have a specific need for that, leave this disabled
42 * so that any length buffer can be compressed.
43 */
44static bool sw842_strict;
45module_param_named(strict, sw842_strict, bool, 0644);
46
47static u8 comp_ops[OPS_MAX][5] = { /* params size in bits */
48 { I8, N0, N0, N0, 0x19 }, /* 8 */
49 { I4, I4, N0, N0, 0x18 }, /* 18 */
50 { I4, I2, I2, N0, 0x17 }, /* 25 */
51 { I2, I2, I4, N0, 0x13 }, /* 25 */
52 { I2, I2, I2, I2, 0x12 }, /* 32 */
53 { I4, I2, D2, N0, 0x16 }, /* 33 */
54 { I4, D2, I2, N0, 0x15 }, /* 33 */
55 { I2, D2, I4, N0, 0x0e }, /* 33 */
56 { D2, I2, I4, N0, 0x09 }, /* 33 */
57 { I2, I2, I2, D2, 0x11 }, /* 40 */
58 { I2, I2, D2, I2, 0x10 }, /* 40 */
59 { I2, D2, I2, I2, 0x0d }, /* 40 */
60 { D2, I2, I2, I2, 0x08 }, /* 40 */
61 { I4, D4, N0, N0, 0x14 }, /* 41 */
62 { D4, I4, N0, N0, 0x04 }, /* 41 */
63 { I2, I2, D4, N0, 0x0f }, /* 48 */
64 { I2, D2, I2, D2, 0x0c }, /* 48 */
65 { I2, D4, I2, N0, 0x0b }, /* 48 */
66 { D2, I2, I2, D2, 0x07 }, /* 48 */
67 { D2, I2, D2, I2, 0x06 }, /* 48 */
68 { D4, I2, I2, N0, 0x03 }, /* 48 */
69 { I2, D2, D4, N0, 0x0a }, /* 56 */
70 { D2, I2, D4, N0, 0x05 }, /* 56 */
71 { D4, I2, D2, N0, 0x02 }, /* 56 */
72 { D4, D2, I2, N0, 0x01 }, /* 56 */
73 { D8, N0, N0, N0, 0x00 }, /* 64 */
74};
75
76struct sw842_hlist_node8 {
77 struct hlist_node node;
78 u64 data;
79 u8 index;
80};
81
82struct sw842_hlist_node4 {
83 struct hlist_node node;
84 u32 data;
85 u16 index;
86};
87
88struct sw842_hlist_node2 {
89 struct hlist_node node;
90 u16 data;
91 u8 index;
92};
93
94#define INDEX_NOT_FOUND (-1)
95#define INDEX_NOT_CHECKED (-2)
96
97struct sw842_param {
98 u8 *in;
99 u8 *instart;
100 u64 ilen;
101 u8 *out;
102 u64 olen;
103 u8 bit;
104 u64 data8[1];
105 u32 data4[2];
106 u16 data2[4];
107 int index8[1];
108 int index4[2];
109 int index2[4];
110 DECLARE_HASHTABLE(htable8, SW842_HASHTABLE8_BITS);
111 DECLARE_HASHTABLE(htable4, SW842_HASHTABLE4_BITS);
112 DECLARE_HASHTABLE(htable2, SW842_HASHTABLE2_BITS);
113 struct sw842_hlist_node8 node8[1 << I8_BITS];
114 struct sw842_hlist_node4 node4[1 << I4_BITS];
115 struct sw842_hlist_node2 node2[1 << I2_BITS];
116};
117
118#define get_input_data(p, o, b) \
119 be##b##_to_cpu(get_unaligned((__be##b *)((p)->in + (o))))
120
121#define init_hashtable_nodes(p, b) do { \
122 int _i; \
123 hash_init((p)->htable##b); \
124 for (_i = 0; _i < ARRAY_SIZE((p)->node##b); _i++) { \
125 (p)->node##b[_i].index = _i; \
126 (p)->node##b[_i].data = 0; \
127 INIT_HLIST_NODE(&(p)->node##b[_i].node); \
128 } \
129} while (0)
130
131#define find_index(p, b, n) ({ \
132 struct sw842_hlist_node##b *_n; \
133 p->index##b[n] = INDEX_NOT_FOUND; \
134 hash_for_each_possible(p->htable##b, _n, node, p->data##b[n]) { \
135 if (p->data##b[n] == _n->data) { \
136 p->index##b[n] = _n->index; \
137 break; \
138 } \
139 } \
140 p->index##b[n] >= 0; \
141})
142
143#define check_index(p, b, n) \
144 ((p)->index##b[n] == INDEX_NOT_CHECKED \
145 ? find_index(p, b, n) \
146 : (p)->index##b[n] >= 0)
147
148#define replace_hash(p, b, i, d) do { \
149 struct sw842_hlist_node##b *_n = &(p)->node##b[(i)+(d)]; \
150 hash_del(&_n->node); \
151 _n->data = (p)->data##b[d]; \
152 pr_debug("add hash index%x %x pos %x data %lx\n", b, \
153 (unsigned int)_n->index, \
154 (unsigned int)((p)->in - (p)->instart), \
155 (unsigned long)_n->data); \
156 hash_add((p)->htable##b, &_n->node, _n->data); \
157} while (0)
158
159static u8 bmask[8] = { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe };
160
161static int add_bits(struct sw842_param *p, u64 d, u8 n);
162
163static int __split_add_bits(struct sw842_param *p, u64 d, u8 n, u8 s)
164{
165 int ret;
166
167 if (n <= s)
168 return -EINVAL;
169
170 ret = add_bits(p, d >> s, n - s);
171 if (ret)
172 return ret;
173 return add_bits(p, d & GENMASK_ULL(s - 1, 0), s);
174}
175
176static int add_bits(struct sw842_param *p, u64 d, u8 n)
177{
178 int b = p->bit, bits = b + n, s = round_up(bits, 8) - bits;
179 u64 o;
180 u8 *out = p->out;
181
182 pr_debug("add %u bits %lx\n", (unsigned char)n, (unsigned long)d);
183
184 if (n > 64)
185 return -EINVAL;
186
187 /* split this up if writing to > 8 bytes (i.e. n == 64 && p->bit > 0),
188 * or if we're at the end of the output buffer and would write past end
189 */
190 if (bits > 64)
191 return __split_add_bits(p, d, n, 32);
192 else if (p->olen < 8 && bits > 32 && bits <= 56)
193 return __split_add_bits(p, d, n, 16);
194 else if (p->olen < 4 && bits > 16 && bits <= 24)
195 return __split_add_bits(p, d, n, 8);
196
197 if (DIV_ROUND_UP(bits, 8) > p->olen)
198 return -ENOSPC;
199
200 o = *out & bmask[b];
201 d <<= s;
202
203 if (bits <= 8)
204 *out = o | d;
205 else if (bits <= 16)
206 put_unaligned(cpu_to_be16(o << 8 | d), (__be16 *)out);
207 else if (bits <= 24)
208 put_unaligned(cpu_to_be32(o << 24 | d << 8), (__be32 *)out);
209 else if (bits <= 32)
210 put_unaligned(cpu_to_be32(o << 24 | d), (__be32 *)out);
211 else if (bits <= 40)
212 put_unaligned(cpu_to_be64(o << 56 | d << 24), (__be64 *)out);
213 else if (bits <= 48)
214 put_unaligned(cpu_to_be64(o << 56 | d << 16), (__be64 *)out);
215 else if (bits <= 56)
216 put_unaligned(cpu_to_be64(o << 56 | d << 8), (__be64 *)out);
217 else
218 put_unaligned(cpu_to_be64(o << 56 | d), (__be64 *)out);
219
220 p->bit += n;
221
222 if (p->bit > 7) {
223 p->out += p->bit / 8;
224 p->olen -= p->bit / 8;
225 p->bit %= 8;
226 }
227
228 return 0;
229}
230
231static int add_template(struct sw842_param *p, u8 c)
232{
233 int ret, i, b = 0;
234 u8 *t = comp_ops[c];
235 bool inv = false;
236
237 if (c >= OPS_MAX)
238 return -EINVAL;
239
240 pr_debug("template %x\n", t[4]);
241
242 ret = add_bits(p, t[4], OP_BITS);
243 if (ret)
244 return ret;
245
246 for (i = 0; i < 4; i++) {
247 pr_debug("op %x\n", t[i]);
248
249 switch (t[i] & OP_AMOUNT) {
250 case OP_AMOUNT_8:
251 if (b)
252 inv = true;
253 else if (t[i] & OP_ACTION_INDEX)
254 ret = add_bits(p, p->index8[0], I8_BITS);
255 else if (t[i] & OP_ACTION_DATA)
256 ret = add_bits(p, p->data8[0], 64);
257 else
258 inv = true;
259 break;
260 case OP_AMOUNT_4:
261 if (b == 2 && t[i] & OP_ACTION_DATA)
262 ret = add_bits(p, get_input_data(p, 2, 32), 32);
263 else if (b != 0 && b != 4)
264 inv = true;
265 else if (t[i] & OP_ACTION_INDEX)
266 ret = add_bits(p, p->index4[b >> 2], I4_BITS);
267 else if (t[i] & OP_ACTION_DATA)
268 ret = add_bits(p, p->data4[b >> 2], 32);
269 else
270 inv = true;
271 break;
272 case OP_AMOUNT_2:
273 if (b != 0 && b != 2 && b != 4 && b != 6)
274 inv = true;
275 if (t[i] & OP_ACTION_INDEX)
276 ret = add_bits(p, p->index2[b >> 1], I2_BITS);
277 else if (t[i] & OP_ACTION_DATA)
278 ret = add_bits(p, p->data2[b >> 1], 16);
279 else
280 inv = true;
281 break;
282 case OP_AMOUNT_0:
283 inv = (b != 8) || !(t[i] & OP_ACTION_NOOP);
284 break;
285 default:
286 inv = true;
287 break;
288 }
289
290 if (ret)
291 return ret;
292
293 if (inv) {
294 pr_err("Invalid templ %x op %d : %x %x %x %x\n",
295 c, i, t[0], t[1], t[2], t[3]);
296 return -EINVAL;
297 }
298
299 b += t[i] & OP_AMOUNT;
300 }
301
302 if (b != 8) {
303 pr_err("Invalid template %x len %x : %x %x %x %x\n",
304 c, b, t[0], t[1], t[2], t[3]);
305 return -EINVAL;
306 }
307
308 if (sw842_template_counts)
309 atomic_inc(&template_count[t[4]]);
310
311 return 0;
312}
313
314static int add_repeat_template(struct sw842_param *p, u8 r)
315{
316 int ret;
317
318 /* repeat param is 0-based */
319 if (!r || --r > REPEAT_BITS_MAX)
320 return -EINVAL;
321
322 ret = add_bits(p, OP_REPEAT, OP_BITS);
323 if (ret)
324 return ret;
325
326 ret = add_bits(p, r, REPEAT_BITS);
327 if (ret)
328 return ret;
329
330 if (sw842_template_counts)
331 atomic_inc(&template_repeat_count);
332
333 return 0;
334}
335
336static int add_short_data_template(struct sw842_param *p, u8 b)
337{
338 int ret, i;
339
340 if (!b || b > SHORT_DATA_BITS_MAX)
341 return -EINVAL;
342
343 ret = add_bits(p, OP_SHORT_DATA, OP_BITS);
344 if (ret)
345 return ret;
346
347 ret = add_bits(p, b, SHORT_DATA_BITS);
348 if (ret)
349 return ret;
350
351 for (i = 0; i < b; i++) {
352 ret = add_bits(p, p->in[i], 8);
353 if (ret)
354 return ret;
355 }
356
357 if (sw842_template_counts)
358 atomic_inc(&template_short_data_count);
359
360 return 0;
361}
362
363static int add_zeros_template(struct sw842_param *p)
364{
365 int ret = add_bits(p, OP_ZEROS, OP_BITS);
366
367 if (ret)
368 return ret;
369
370 if (sw842_template_counts)
371 atomic_inc(&template_zeros_count);
372
373 return 0;
374}
375
376static int add_end_template(struct sw842_param *p)
377{
378 int ret = add_bits(p, OP_END, OP_BITS);
379
380 if (ret)
381 return ret;
382
383 if (sw842_template_counts)
384 atomic_inc(&template_end_count);
385
386 return 0;
387}
388
389static bool check_template(struct sw842_param *p, u8 c)
390{
391 u8 *t = comp_ops[c];
392 int i, match, b = 0;
393
394 if (c >= OPS_MAX)
395 return false;
396
397 for (i = 0; i < 4; i++) {
398 if (t[i] & OP_ACTION_INDEX) {
399 if (t[i] & OP_AMOUNT_2)
400 match = check_index(p, 2, b >> 1);
401 else if (t[i] & OP_AMOUNT_4)
402 match = check_index(p, 4, b >> 2);
403 else if (t[i] & OP_AMOUNT_8)
404 match = check_index(p, 8, 0);
405 else
406 return false;
407 if (!match)
408 return false;
409 }
410
411 b += t[i] & OP_AMOUNT;
412 }
413
414 return true;
415}
416
417static void get_next_data(struct sw842_param *p)
418{
419 p->data8[0] = get_input_data(p, 0, 64);
420 p->data4[0] = get_input_data(p, 0, 32);
421 p->data4[1] = get_input_data(p, 4, 32);
422 p->data2[0] = get_input_data(p, 0, 16);
423 p->data2[1] = get_input_data(p, 2, 16);
424 p->data2[2] = get_input_data(p, 4, 16);
425 p->data2[3] = get_input_data(p, 6, 16);
426}
427
428/* update the hashtable entries.
429 * only call this after finding/adding the current template
430 * the dataN fields for the current 8 byte block must be already updated
431 */
432static void update_hashtables(struct sw842_param *p)
433{
434 u64 pos = p->in - p->instart;
435 u64 n8 = (pos >> 3) % (1 << I8_BITS);
436 u64 n4 = (pos >> 2) % (1 << I4_BITS);
437 u64 n2 = (pos >> 1) % (1 << I2_BITS);
438
439 replace_hash(p, 8, n8, 0);
440 replace_hash(p, 4, n4, 0);
441 replace_hash(p, 4, n4, 1);
442 replace_hash(p, 2, n2, 0);
443 replace_hash(p, 2, n2, 1);
444 replace_hash(p, 2, n2, 2);
445 replace_hash(p, 2, n2, 3);
446}
447
448/* find the next template to use, and add it
449 * the p->dataN fields must already be set for the current 8 byte block
450 */
451static int process_next(struct sw842_param *p)
452{
453 int ret, i;
454
455 p->index8[0] = INDEX_NOT_CHECKED;
456 p->index4[0] = INDEX_NOT_CHECKED;
457 p->index4[1] = INDEX_NOT_CHECKED;
458 p->index2[0] = INDEX_NOT_CHECKED;
459 p->index2[1] = INDEX_NOT_CHECKED;
460 p->index2[2] = INDEX_NOT_CHECKED;
461 p->index2[3] = INDEX_NOT_CHECKED;
462
463 /* check up to OPS_MAX - 1; last op is our fallback */
464 for (i = 0; i < OPS_MAX - 1; i++) {
465 if (check_template(p, i))
466 break;
467 }
468
469 ret = add_template(p, i);
470 if (ret)
471 return ret;
472
473 return 0;
474}
475
476/**
477 * sw842_compress
478 *
479 * Compress the uncompressed buffer of length @ilen at @in to the output buffer
480 * @out, using no more than @olen bytes, using the 842 compression format.
481 *
482 * Returns: 0 on success, error on failure. The @olen parameter
483 * will contain the number of output bytes written on success, or
484 * 0 on error.
485 */
486int sw842_compress(const u8 *in, unsigned int ilen,
487 u8 *out, unsigned int *olen, void *wmem)
488{
489 struct sw842_param *p = (struct sw842_param *)wmem;
490 int ret;
491 u64 last, next, pad, total;
492 u8 repeat_count = 0;
493
494 BUILD_BUG_ON(sizeof(*p) > SW842_MEM_COMPRESS);
495
496 init_hashtable_nodes(p, 8);
497 init_hashtable_nodes(p, 4);
498 init_hashtable_nodes(p, 2);
499
500 p->in = (u8 *)in;
501 p->instart = p->in;
502 p->ilen = ilen;
503 p->out = out;
504 p->olen = *olen;
505 p->bit = 0;
506
507 total = p->olen;
508
509 *olen = 0;
510
511 /* if using strict mode, we can only compress a multiple of 8 */
512 if (sw842_strict && (ilen % 8)) {
513 pr_err("Using strict mode, can't compress len %d\n", ilen);
514 return -EINVAL;
515 }
516
517 /* let's compress at least 8 bytes, mkay? */
518 if (unlikely(ilen < 8))
519 goto skip_comp;
520
521 /* make initial 'last' different so we don't match the first time */
522 last = ~get_unaligned((u64 *)p->in);
523
524 while (p->ilen > 7) {
525 next = get_unaligned((u64 *)p->in);
526
527 /* must get the next data, as we need to update the hashtable
528 * entries with the new data every time
529 */
530 get_next_data(p);
531
532 /* we don't care about endianness in last or next;
533 * we're just comparing 8 bytes to another 8 bytes,
534 * they're both the same endianness
535 */
536 if (next == last) {
537 /* repeat count bits are 0-based, so we stop at +1 */
538 if (++repeat_count <= REPEAT_BITS_MAX)
539 goto repeat;
540 }
541 if (repeat_count) {
542 ret = add_repeat_template(p, repeat_count);
543 repeat_count = 0;
544 if (next == last) /* reached max repeat bits */
545 goto repeat;
546 }
547
548 if (next == 0)
549 ret = add_zeros_template(p);
550 else
551 ret = process_next(p);
552
553 if (ret)
554 return ret;
555
556repeat:
557 last = next;
558 update_hashtables(p);
559 p->in += 8;
560 p->ilen -= 8;
561 }
562
563 if (repeat_count) {
564 ret = add_repeat_template(p, repeat_count);
565 if (ret)
566 return ret;
567 }
568
569skip_comp:
570 if (p->ilen > 0) {
571 ret = add_short_data_template(p, p->ilen);
572 if (ret)
573 return ret;
574
575 p->in += p->ilen;
576 p->ilen = 0;
577 }
578
579 ret = add_end_template(p);
580 if (ret)
581 return ret;
582
583 if (p->bit) {
584 p->out++;
585 p->olen--;
586 p->bit = 0;
587 }
588
589 /* pad compressed length to multiple of 8 */
590 pad = (8 - ((total - p->olen) % 8)) % 8;
591 if (pad) {
592 if (pad > p->olen) /* we were so close! */
593 return -ENOSPC;
594 memset(p->out, 0, pad);
595 p->out += pad;
596 p->olen -= pad;
597 }
598
599 if (unlikely((total - p->olen) > UINT_MAX))
600 return -ENOSPC;
601
602 *olen = total - p->olen;
603
604 return 0;
605}
606EXPORT_SYMBOL_GPL(sw842_compress);
607
608static int __init sw842_init(void)
609{
610 if (sw842_template_counts)
611 sw842_debugfs_create();
612
613 return 0;
614}
615module_init(sw842_init);
616
617static void __exit sw842_exit(void)
618{
619 if (sw842_template_counts)
620 sw842_debugfs_remove();
621}
622module_exit(sw842_exit);
623
624MODULE_LICENSE("GPL");
625MODULE_DESCRIPTION("Software 842 Compressor");
626MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");
diff --git a/lib/842/842_debugfs.h b/lib/842/842_debugfs.h
new file mode 100644
index 000000000000..e7f3bffaf255
--- /dev/null
+++ b/lib/842/842_debugfs.h
@@ -0,0 +1,52 @@
1
2#ifndef __842_DEBUGFS_H__
3#define __842_DEBUGFS_H__
4
5#include <linux/debugfs.h>
6
7static bool sw842_template_counts;
8module_param_named(template_counts, sw842_template_counts, bool, 0444);
9
10static atomic_t template_count[OPS_MAX], template_repeat_count,
11 template_zeros_count, template_short_data_count, template_end_count;
12
13static struct dentry *sw842_debugfs_root;
14
15static int __init sw842_debugfs_create(void)
16{
17 umode_t m = S_IRUGO | S_IWUSR;
18 int i;
19
20 if (!debugfs_initialized())
21 return -ENODEV;
22
23 sw842_debugfs_root = debugfs_create_dir(MODULE_NAME, NULL);
24 if (IS_ERR(sw842_debugfs_root))
25 return PTR_ERR(sw842_debugfs_root);
26
27 for (i = 0; i < ARRAY_SIZE(template_count); i++) {
28 char name[32];
29
30 snprintf(name, 32, "template_%02x", i);
31 debugfs_create_atomic_t(name, m, sw842_debugfs_root,
32 &template_count[i]);
33 }
34 debugfs_create_atomic_t("template_repeat", m, sw842_debugfs_root,
35 &template_repeat_count);
36 debugfs_create_atomic_t("template_zeros", m, sw842_debugfs_root,
37 &template_zeros_count);
38 debugfs_create_atomic_t("template_short_data", m, sw842_debugfs_root,
39 &template_short_data_count);
40 debugfs_create_atomic_t("template_end", m, sw842_debugfs_root,
41 &template_end_count);
42
43 return 0;
44}
45
46static void __exit sw842_debugfs_remove(void)
47{
48 if (sw842_debugfs_root && !IS_ERR(sw842_debugfs_root))
49 debugfs_remove_recursive(sw842_debugfs_root);
50}
51
52#endif
diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
new file mode 100644
index 000000000000..5446ff0c9ba0
--- /dev/null
+++ b/lib/842/842_decompress.c
@@ -0,0 +1,405 @@
1/*
2 * 842 Software Decompression
3 *
4 * Copyright (C) 2015 Dan Streetman, IBM Corp
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * See 842.h for details of the 842 compressed format.
17 */
18
19#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
20#define MODULE_NAME "842_decompress"
21
22#include "842.h"
23#include "842_debugfs.h"
24
25/* rolling fifo sizes */
26#define I2_FIFO_SIZE (2 * (1 << I2_BITS))
27#define I4_FIFO_SIZE (4 * (1 << I4_BITS))
28#define I8_FIFO_SIZE (8 * (1 << I8_BITS))
29
30static u8 decomp_ops[OPS_MAX][4] = {
31 { D8, N0, N0, N0 },
32 { D4, D2, I2, N0 },
33 { D4, I2, D2, N0 },
34 { D4, I2, I2, N0 },
35 { D4, I4, N0, N0 },
36 { D2, I2, D4, N0 },
37 { D2, I2, D2, I2 },
38 { D2, I2, I2, D2 },
39 { D2, I2, I2, I2 },
40 { D2, I2, I4, N0 },
41 { I2, D2, D4, N0 },
42 { I2, D4, I2, N0 },
43 { I2, D2, I2, D2 },
44 { I2, D2, I2, I2 },
45 { I2, D2, I4, N0 },
46 { I2, I2, D4, N0 },
47 { I2, I2, D2, I2 },
48 { I2, I2, I2, D2 },
49 { I2, I2, I2, I2 },
50 { I2, I2, I4, N0 },
51 { I4, D4, N0, N0 },
52 { I4, D2, I2, N0 },
53 { I4, I2, D2, N0 },
54 { I4, I2, I2, N0 },
55 { I4, I4, N0, N0 },
56 { I8, N0, N0, N0 }
57};
58
59struct sw842_param {
60 u8 *in;
61 u8 bit;
62 u64 ilen;
63 u8 *out;
64 u8 *ostart;
65 u64 olen;
66};
67
68#define beN_to_cpu(d, s) \
69 ((s) == 2 ? be16_to_cpu(get_unaligned((__be16 *)d)) : \
70 (s) == 4 ? be32_to_cpu(get_unaligned((__be32 *)d)) : \
71 (s) == 8 ? be64_to_cpu(get_unaligned((__be64 *)d)) : \
72 WARN(1, "pr_debug param err invalid size %x\n", s))
73
74static int next_bits(struct sw842_param *p, u64 *d, u8 n);
75
76static int __split_next_bits(struct sw842_param *p, u64 *d, u8 n, u8 s)
77{
78 u64 tmp = 0;
79 int ret;
80
81 if (n <= s) {
82 pr_debug("split_next_bits invalid n %u s %u\n", n, s);
83 return -EINVAL;
84 }
85
86 ret = next_bits(p, &tmp, n - s);
87 if (ret)
88 return ret;
89 ret = next_bits(p, d, s);
90 if (ret)
91 return ret;
92 *d |= tmp << s;
93 return 0;
94}
95
96static int next_bits(struct sw842_param *p, u64 *d, u8 n)
97{
98 u8 *in = p->in, b = p->bit, bits = b + n;
99
100 if (n > 64) {
101 pr_debug("next_bits invalid n %u\n", n);
102 return -EINVAL;
103 }
104
105 /* split this up if reading > 8 bytes, or if we're at the end of
106 * the input buffer and would read past the end
107 */
108 if (bits > 64)
109 return __split_next_bits(p, d, n, 32);
110 else if (p->ilen < 8 && bits > 32 && bits <= 56)
111 return __split_next_bits(p, d, n, 16);
112 else if (p->ilen < 4 && bits > 16 && bits <= 24)
113 return __split_next_bits(p, d, n, 8);
114
115 if (DIV_ROUND_UP(bits, 8) > p->ilen)
116 return -EOVERFLOW;
117
118 if (bits <= 8)
119 *d = *in >> (8 - bits);
120 else if (bits <= 16)
121 *d = be16_to_cpu(get_unaligned((__be16 *)in)) >> (16 - bits);
122 else if (bits <= 32)
123 *d = be32_to_cpu(get_unaligned((__be32 *)in)) >> (32 - bits);
124 else
125 *d = be64_to_cpu(get_unaligned((__be64 *)in)) >> (64 - bits);
126
127 *d &= GENMASK_ULL(n - 1, 0);
128
129 p->bit += n;
130
131 if (p->bit > 7) {
132 p->in += p->bit / 8;
133 p->ilen -= p->bit / 8;
134 p->bit %= 8;
135 }
136
137 return 0;
138}
139
140static int do_data(struct sw842_param *p, u8 n)
141{
142 u64 v;
143 int ret;
144
145 if (n > p->olen)
146 return -ENOSPC;
147
148 ret = next_bits(p, &v, n * 8);
149 if (ret)
150 return ret;
151
152 switch (n) {
153 case 2:
154 put_unaligned(cpu_to_be16((u16)v), (__be16 *)p->out);
155 break;
156 case 4:
157 put_unaligned(cpu_to_be32((u32)v), (__be32 *)p->out);
158 break;
159 case 8:
160 put_unaligned(cpu_to_be64((u64)v), (__be64 *)p->out);
161 break;
162 default:
163 return -EINVAL;
164 }
165
166 p->out += n;
167 p->olen -= n;
168
169 return 0;
170}
171
172static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
173{
174 u64 index, offset, total = round_down(p->out - p->ostart, 8);
175 int ret;
176
177 ret = next_bits(p, &index, bits);
178 if (ret)
179 return ret;
180
181 offset = index * size;
182
183 /* a ring buffer of fsize is used; correct the offset */
184 if (total > fsize) {
185 /* this is where the current fifo is */
186 u64 section = round_down(total, fsize);
187 /* the current pos in the fifo */
188 u64 pos = total - section;
189
190 /* if the offset is past/at the pos, we need to
191 * go back to the last fifo section
192 */
193 if (offset >= pos)
194 section -= fsize;
195
196 offset += section;
197 }
198
199 if (offset + size > total) {
200 pr_debug("index%x %lx points past end %lx\n", size,
201 (unsigned long)offset, (unsigned long)total);
202 return -EINVAL;
203 }
204
205 pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n",
206 size, (unsigned long)index, (unsigned long)(index * size),
207 (unsigned long)offset, (unsigned long)total,
208 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
209
210 memcpy(p->out, &p->ostart[offset], size);
211 p->out += size;
212 p->olen -= size;
213
214 return 0;
215}
216
217static int do_index(struct sw842_param *p, u8 n)
218{
219 switch (n) {
220 case 2:
221 return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE);
222 case 4:
223 return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE);
224 case 8:
225 return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE);
226 default:
227 return -EINVAL;
228 }
229}
230
231static int do_op(struct sw842_param *p, u8 o)
232{
233 int i, ret = 0;
234
235 if (o >= OPS_MAX)
236 return -EINVAL;
237
238 for (i = 0; i < 4; i++) {
239 u8 op = decomp_ops[o][i];
240
241 pr_debug("op is %x\n", op);
242
243 switch (op & OP_ACTION) {
244 case OP_ACTION_DATA:
245 ret = do_data(p, op & OP_AMOUNT);
246 break;
247 case OP_ACTION_INDEX:
248 ret = do_index(p, op & OP_AMOUNT);
249 break;
250 case OP_ACTION_NOOP:
251 break;
252 default:
253 pr_err("Interal error, invalid op %x\n", op);
254 return -EINVAL;
255 }
256
257 if (ret)
258 return ret;
259 }
260
261 if (sw842_template_counts)
262 atomic_inc(&template_count[o]);
263
264 return 0;
265}
266
267/**
268 * sw842_decompress
269 *
270 * Decompress the 842-compressed buffer of length @ilen at @in
271 * to the output buffer @out, using no more than @olen bytes.
272 *
273 * The compressed buffer must be only a single 842-compressed buffer,
274 * with the standard format described in the comments in 842.h
275 * Processing will stop when the 842 "END" template is detected,
276 * not the end of the buffer.
277 *
278 * Returns: 0 on success, error on failure. The @olen parameter
279 * will contain the number of output bytes written on success, or
280 * 0 on error.
281 */
282int sw842_decompress(const u8 *in, unsigned int ilen,
283 u8 *out, unsigned int *olen)
284{
285 struct sw842_param p;
286 int ret;
287 u64 op, rep, tmp, bytes, total;
288
289 p.in = (u8 *)in;
290 p.bit = 0;
291 p.ilen = ilen;
292 p.out = out;
293 p.ostart = out;
294 p.olen = *olen;
295
296 total = p.olen;
297
298 *olen = 0;
299
300 do {
301 ret = next_bits(&p, &op, OP_BITS);
302 if (ret)
303 return ret;
304
305 pr_debug("template is %lx\n", (unsigned long)op);
306
307 switch (op) {
308 case OP_REPEAT:
309 ret = next_bits(&p, &rep, REPEAT_BITS);
310 if (ret)
311 return ret;
312
313 if (p.out == out) /* no previous bytes */
314 return -EINVAL;
315
316 /* copy rep + 1 */
317 rep++;
318
319 if (rep * 8 > p.olen)
320 return -ENOSPC;
321
322 while (rep-- > 0) {
323 memcpy(p.out, p.out - 8, 8);
324 p.out += 8;
325 p.olen -= 8;
326 }
327
328 if (sw842_template_counts)
329 atomic_inc(&template_repeat_count);
330
331 break;
332 case OP_ZEROS:
333 if (8 > p.olen)
334 return -ENOSPC;
335
336 memset(p.out, 0, 8);
337 p.out += 8;
338 p.olen -= 8;
339
340 if (sw842_template_counts)
341 atomic_inc(&template_zeros_count);
342
343 break;
344 case OP_SHORT_DATA:
345 ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
346 if (ret)
347 return ret;
348
349 if (!bytes || bytes > SHORT_DATA_BITS_MAX)
350 return -EINVAL;
351
352 while (bytes-- > 0) {
353 ret = next_bits(&p, &tmp, 8);
354 if (ret)
355 return ret;
356 *p.out = (u8)tmp;
357 p.out++;
358 p.olen--;
359 }
360
361 if (sw842_template_counts)
362 atomic_inc(&template_short_data_count);
363
364 break;
365 case OP_END:
366 if (sw842_template_counts)
367 atomic_inc(&template_end_count);
368
369 break;
370 default: /* use template */
371 ret = do_op(&p, op);
372 if (ret)
373 return ret;
374 break;
375 }
376 } while (op != OP_END);
377
378 if (unlikely((total - p.olen) > UINT_MAX))
379 return -ENOSPC;
380
381 *olen = total - p.olen;
382
383 return 0;
384}
385EXPORT_SYMBOL_GPL(sw842_decompress);
386
387static int __init sw842_init(void)
388{
389 if (sw842_template_counts)
390 sw842_debugfs_create();
391
392 return 0;
393}
394module_init(sw842_init);
395
396static void __exit sw842_exit(void)
397{
398 if (sw842_template_counts)
399 sw842_debugfs_remove();
400}
401module_exit(sw842_exit);
402
403MODULE_LICENSE("GPL");
404MODULE_DESCRIPTION("Software 842 Decompressor");
405MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");
diff --git a/lib/842/Makefile b/lib/842/Makefile
new file mode 100644
index 000000000000..5d24c0baff2e
--- /dev/null
+++ b/lib/842/Makefile
@@ -0,0 +1,2 @@
1obj-$(CONFIG_842_COMPRESS) += 842_compress.o
2obj-$(CONFIG_842_DECOMPRESS) += 842_decompress.o
diff --git a/lib/Kconfig b/lib/Kconfig
index 601965a948e8..34e332b8d326 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -212,6 +212,12 @@ config RANDOM32_SELFTEST
212# 212#
213# compression support is select'ed if needed 213# compression support is select'ed if needed
214# 214#
215config 842_COMPRESS
216 tristate
217
218config 842_DECOMPRESS
219 tristate
220
215config ZLIB_INFLATE 221config ZLIB_INFLATE
216 tristate 222 tristate
217 223
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index ba2b0c87e65b..b908048f8d6a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1233,6 +1233,7 @@ config RCU_TORTURE_TEST
1233 depends on DEBUG_KERNEL 1233 depends on DEBUG_KERNEL
1234 select TORTURE_TEST 1234 select TORTURE_TEST
1235 select SRCU 1235 select SRCU
1236 select TASKS_RCU
1236 default n 1237 default n
1237 help 1238 help
1238 This option provides a kernel module that runs torture tests 1239 This option provides a kernel module that runs torture tests
@@ -1261,12 +1262,38 @@ config RCU_TORTURE_TEST_RUNNABLE
1261 Say N here if you want the RCU torture tests to start only 1262 Say N here if you want the RCU torture tests to start only
1262 after being manually enabled via /proc. 1263 after being manually enabled via /proc.
1263 1264
1265config RCU_TORTURE_TEST_SLOW_PREINIT
1266 bool "Slow down RCU grace-period pre-initialization to expose races"
1267 depends on RCU_TORTURE_TEST
1268 help
1269 This option delays grace-period pre-initialization (the
1270 propagation of CPU-hotplug changes up the rcu_node combining
1271 tree) for a few jiffies between initializing each pair of
1272 consecutive rcu_node structures. This helps to expose races
1273 involving grace-period pre-initialization, in other words, it
1274 makes your kernel less stable. It can also greatly increase
1275 grace-period latency, especially on systems with large numbers
1276 of CPUs. This is useful when torture-testing RCU, but in
1277 almost no other circumstance.
1278
1279 Say Y here if you want your system to crash and hang more often.
1280 Say N if you want a sane system.
1281
1282config RCU_TORTURE_TEST_SLOW_PREINIT_DELAY
1283 int "How much to slow down RCU grace-period pre-initialization"
1284 range 0 5
1285 default 3
1286 depends on RCU_TORTURE_TEST_SLOW_PREINIT
1287 help
1288 This option specifies the number of jiffies to wait between
1289 each rcu_node structure pre-initialization step.
1290
1264config RCU_TORTURE_TEST_SLOW_INIT 1291config RCU_TORTURE_TEST_SLOW_INIT
1265 bool "Slow down RCU grace-period initialization to expose races" 1292 bool "Slow down RCU grace-period initialization to expose races"
1266 depends on RCU_TORTURE_TEST 1293 depends on RCU_TORTURE_TEST
1267 help 1294 help
1268 This option makes grace-period initialization block for a 1295 This option delays grace-period initialization for a few
1269 few jiffies between initializing each pair of consecutive 1296 jiffies between initializing each pair of consecutive
1270 rcu_node structures. This helps to expose races involving 1297 rcu_node structures. This helps to expose races involving
1271 grace-period initialization, in other words, it makes your 1298 grace-period initialization, in other words, it makes your
1272 kernel less stable. It can also greatly increase grace-period 1299 kernel less stable. It can also greatly increase grace-period
@@ -1286,6 +1313,30 @@ config RCU_TORTURE_TEST_SLOW_INIT_DELAY
1286 This option specifies the number of jiffies to wait between 1313 This option specifies the number of jiffies to wait between
1287 each rcu_node structure initialization. 1314 each rcu_node structure initialization.
1288 1315
1316config RCU_TORTURE_TEST_SLOW_CLEANUP
1317 bool "Slow down RCU grace-period cleanup to expose races"
1318 depends on RCU_TORTURE_TEST
1319 help
1320 This option delays grace-period cleanup for a few jiffies
1321 between cleaning up each pair of consecutive rcu_node
1322 structures. This helps to expose races involving grace-period
1323 cleanup, in other words, it makes your kernel less stable.
1324 It can also greatly increase grace-period latency, especially
1325 on systems with large numbers of CPUs. This is useful when
1326 torture-testing RCU, but in almost no other circumstance.
1327
1328 Say Y here if you want your system to crash and hang more often.
1329 Say N if you want a sane system.
1330
1331config RCU_TORTURE_TEST_SLOW_CLEANUP_DELAY
1332 int "How much to slow down RCU grace-period cleanup"
1333 range 0 5
1334 default 3
1335 depends on RCU_TORTURE_TEST_SLOW_CLEANUP
1336 help
1337 This option specifies the number of jiffies to wait between
1338 each rcu_node structure cleanup operation.
1339
1289config RCU_CPU_STALL_TIMEOUT 1340config RCU_CPU_STALL_TIMEOUT
1290 int "RCU CPU stall timeout in seconds" 1341 int "RCU CPU stall timeout in seconds"
1291 depends on RCU_STALL_COMMON 1342 depends on RCU_STALL_COMMON
@@ -1322,6 +1373,17 @@ config RCU_TRACE
1322 Say Y here if you want to enable RCU tracing 1373 Say Y here if you want to enable RCU tracing
1323 Say N if you are unsure. 1374 Say N if you are unsure.
1324 1375
1376config RCU_EQS_DEBUG
1377 bool "Use this when adding any sort of NO_HZ support to your arch"
1378 depends on DEBUG_KERNEL
1379 help
1380 This option provides consistency checks in RCU's handling of
1381 NO_HZ. These checks have proven quite helpful in detecting
1382 bugs in arch-specific NO_HZ code.
1383
1384 Say N here if you need ultimate kernel/user switch latencies
1385 Say Y if you are unsure
1386
1325endmenu # "RCU Debugging" 1387endmenu # "RCU Debugging"
1326 1388
1327config DEBUG_BLOCK_EXT_DEVT 1389config DEBUG_BLOCK_EXT_DEVT
diff --git a/lib/Makefile b/lib/Makefile
index 6c37933336a0..ff37c8c2f7b2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -78,6 +78,8 @@ obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
78obj-$(CONFIG_CRC8) += crc8.o 78obj-$(CONFIG_CRC8) += crc8.o
79obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o 79obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
80 80
81obj-$(CONFIG_842_COMPRESS) += 842/
82obj-$(CONFIG_842_DECOMPRESS) += 842/
81obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ 83obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
82obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ 84obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
83obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ 85obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
diff --git a/lib/cpu_rmap.c b/lib/cpu_rmap.c
index 4f134d8907a7..f610b2a10b3e 100644
--- a/lib/cpu_rmap.c
+++ b/lib/cpu_rmap.c
@@ -191,7 +191,7 @@ int cpu_rmap_update(struct cpu_rmap *rmap, u16 index,
191 /* Update distances based on topology */ 191 /* Update distances based on topology */
192 for_each_cpu(cpu, update_mask) { 192 for_each_cpu(cpu, update_mask) {
193 if (cpu_rmap_copy_neigh(rmap, cpu, 193 if (cpu_rmap_copy_neigh(rmap, cpu,
194 topology_thread_cpumask(cpu), 1)) 194 topology_sibling_cpumask(cpu), 1))
195 continue; 195 continue;
196 if (cpu_rmap_copy_neigh(rmap, cpu, 196 if (cpu_rmap_copy_neigh(rmap, cpu,
197 topology_core_cpumask(cpu), 2)) 197 topology_core_cpumask(cpu), 2))
diff --git a/lib/cpumask.c b/lib/cpumask.c
index 5f627084f2e9..5a70f6196f57 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -16,11 +16,10 @@
16int cpumask_next_and(int n, const struct cpumask *src1p, 16int cpumask_next_and(int n, const struct cpumask *src1p,
17 const struct cpumask *src2p) 17 const struct cpumask *src2p)
18{ 18{
19 struct cpumask tmp; 19 while ((n = cpumask_next(n, src1p)) < nr_cpu_ids)
20 20 if (cpumask_test_cpu(n, src2p))
21 if (cpumask_and(&tmp, src1p, src2p)) 21 break;
22 return cpumask_next(n, &tmp); 22 return n;
23 return nr_cpu_ids;
24} 23}
25EXPORT_SYMBOL(cpumask_next_and); 24EXPORT_SYMBOL(cpumask_next_and);
26 25
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
index aac511417ad1..a89d041592c8 100644
--- a/lib/mpi/longlong.h
+++ b/lib/mpi/longlong.h
@@ -639,7 +639,7 @@ do { \
639 ************** MIPS ***************** 639 ************** MIPS *****************
640 ***************************************/ 640 ***************************************/
641#if defined(__mips__) && W_TYPE_SIZE == 32 641#if defined(__mips__) && W_TYPE_SIZE == 32
642#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 4 642#if (__GNUC__ >= 5) || (__GNUC__ >= 4 && __GNUC_MINOR__ >= 4)
643#define umul_ppmm(w1, w0, u, v) \ 643#define umul_ppmm(w1, w0, u, v) \
644do { \ 644do { \
645 UDItype __ll = (UDItype)(u) * (v); \ 645 UDItype __ll = (UDItype)(u) * (v); \
@@ -671,7 +671,7 @@ do { \
671 ************** MIPS/64 ************** 671 ************** MIPS/64 **************
672 ***************************************/ 672 ***************************************/
673#if (defined(__mips) && __mips >= 3) && W_TYPE_SIZE == 64 673#if (defined(__mips) && __mips >= 3) && W_TYPE_SIZE == 64
674#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 4 674#if (__GNUC__ >= 5) || (__GNUC__ >= 4 && __GNUC_MINOR__ >= 4)
675#define umul_ppmm(w1, w0, u, v) \ 675#define umul_ppmm(w1, w0, u, v) \
676do { \ 676do { \
677 typedef unsigned int __ll_UTItype __attribute__((mode(TI))); \ 677 typedef unsigned int __ll_UTItype __attribute__((mode(TI))); \
diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c
index 4cc6442733f4..bc0a1da8afba 100644
--- a/lib/mpi/mpicoder.c
+++ b/lib/mpi/mpicoder.c
@@ -128,28 +128,36 @@ leave:
128} 128}
129EXPORT_SYMBOL_GPL(mpi_read_from_buffer); 129EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
130 130
131/**************** 131/**
132 * Return an allocated buffer with the MPI (msb first). 132 * mpi_read_buffer() - read MPI to a bufer provided by user (msb first)
133 * NBYTES receives the length of this buffer. Caller must free the 133 *
134 * return string (This function does return a 0 byte buffer with NBYTES 134 * @a: a multi precision integer
135 * set to zero if the value of A is zero. If sign is not NULL, it will 135 * @buf: bufer to which the output will be written to. Needs to be at
136 * be set to the sign of the A. 136 * leaset mpi_get_size(a) long.
137 * @buf_len: size of the buf.
138 * @nbytes: receives the actual length of the data written.
139 * @sign: if not NULL, it will be set to the sign of a.
140 *
141 * Return: 0 on success or error code in case of error
137 */ 142 */
138void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign) 143int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
144 int *sign)
139{ 145{
140 uint8_t *p, *buffer; 146 uint8_t *p;
141 mpi_limb_t alimb; 147 mpi_limb_t alimb;
148 unsigned int n = mpi_get_size(a);
142 int i; 149 int i;
143 unsigned int n; 150
151 if (buf_len < n || !buf)
152 return -EINVAL;
144 153
145 if (sign) 154 if (sign)
146 *sign = a->sign; 155 *sign = a->sign;
147 *nbytes = n = a->nlimbs * BYTES_PER_MPI_LIMB; 156
148 if (!n) 157 if (nbytes)
149 n++; /* avoid zero length allocation */ 158 *nbytes = n;
150 p = buffer = kmalloc(n, GFP_KERNEL); 159
151 if (!p) 160 p = buf;
152 return NULL;
153 161
154 for (i = a->nlimbs - 1; i >= 0; i--) { 162 for (i = a->nlimbs - 1; i >= 0; i--) {
155 alimb = a->d[i]; 163 alimb = a->d[i];
@@ -171,15 +179,56 @@ void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
171#error please implement for this limb size. 179#error please implement for this limb size.
172#endif 180#endif
173 } 181 }
182 return 0;
183}
184EXPORT_SYMBOL_GPL(mpi_read_buffer);
185
186/*
187 * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first).
188 * Caller must free the return string.
189 * This function does return a 0 byte buffer with nbytes set to zero if the
190 * value of A is zero.
191 *
192 * @a: a multi precision integer.
193 * @nbytes: receives the length of this buffer.
194 * @sign: if not NULL, it will be set to the sign of the a.
195 *
196 * Return: Pointer to MPI buffer or NULL on error
197 */
198void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
199{
200 uint8_t *buf, *p;
201 unsigned int n;
202 int ret;
203
204 if (!nbytes)
205 return NULL;
206
207 n = mpi_get_size(a);
208
209 if (!n)
210 n++;
211
212 buf = kmalloc(n, GFP_KERNEL);
213
214 if (!buf)
215 return NULL;
216
217 ret = mpi_read_buffer(a, buf, n, nbytes, sign);
218
219 if (ret) {
220 kfree(buf);
221 return NULL;
222 }
174 223
175 /* this is sub-optimal but we need to do the shift operation 224 /* this is sub-optimal but we need to do the shift operation
176 * because the caller has to free the returned buffer */ 225 * because the caller has to free the returned buffer */
177 for (p = buffer; !*p && *nbytes; p++, --*nbytes) 226 for (p = buf; !*p && *nbytes; p++, --*nbytes)
178 ; 227 ;
179 if (p != buffer) 228 if (p != buf)
180 memmove(buffer, p, *nbytes); 229 memmove(buf, p, *nbytes);
181 230
182 return buffer; 231 return buf;
183} 232}
184EXPORT_SYMBOL_GPL(mpi_get_buffer); 233EXPORT_SYMBOL_GPL(mpi_get_buffer);
185 234
diff --git a/lib/mpi/mpiutil.c b/lib/mpi/mpiutil.c
index bf076d281d40..314f4dfa603e 100644
--- a/lib/mpi/mpiutil.c
+++ b/lib/mpi/mpiutil.c
@@ -69,7 +69,7 @@ void mpi_free_limb_space(mpi_ptr_t a)
69 if (!a) 69 if (!a)
70 return; 70 return;
71 71
72 kfree(a); 72 kzfree(a);
73} 73}
74 74
75void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs) 75void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs)
@@ -95,7 +95,7 @@ int mpi_resize(MPI a, unsigned nlimbs)
95 if (!p) 95 if (!p)
96 return -ENOMEM; 96 return -ENOMEM;
97 memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t)); 97 memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t));
98 kfree(a->d); 98 kzfree(a->d);
99 a->d = p; 99 a->d = p;
100 } else { 100 } else {
101 a->d = kzalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL); 101 a->d = kzalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL);
@@ -112,7 +112,7 @@ void mpi_free(MPI a)
112 return; 112 return;
113 113
114 if (a->flags & 4) 114 if (a->flags & 4)
115 kfree(a->d); 115 kzfree(a->d);
116 else 116 else
117 mpi_free_limb_space(a->d); 117 mpi_free_limb_space(a->d);
118 118
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 3d2aa27b845b..061550de77bc 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -33,7 +33,7 @@
33#include <linux/string.h> 33#include <linux/string.h>
34#include <linux/bitops.h> 34#include <linux/bitops.h>
35#include <linux/rcupdate.h> 35#include <linux/rcupdate.h>
36#include <linux/preempt_mask.h> /* in_interrupt() */ 36#include <linux/preempt.h> /* in_interrupt() */
37 37
38 38
39/* 39/*
diff --git a/lib/raid6/x86.h b/lib/raid6/x86.h
index b7595484a815..8fe9d9662abb 100644
--- a/lib/raid6/x86.h
+++ b/lib/raid6/x86.h
@@ -23,7 +23,7 @@
23 23
24#ifdef __KERNEL__ /* Real code */ 24#ifdef __KERNEL__ /* Real code */
25 25
26#include <asm/i387.h> 26#include <asm/fpu/api.h>
27 27
28#else /* Dummy code for user space testing */ 28#else /* Dummy code for user space testing */
29 29
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 4396434e4715..8609378e6505 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -26,6 +26,7 @@
26#include <linux/random.h> 26#include <linux/random.h>
27#include <linux/rhashtable.h> 27#include <linux/rhashtable.h>
28#include <linux/err.h> 28#include <linux/err.h>
29#include <linux/export.h>
29 30
30#define HASH_DEFAULT_SIZE 64UL 31#define HASH_DEFAULT_SIZE 64UL
31#define HASH_MIN_SIZE 4U 32#define HASH_MIN_SIZE 4U
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index c9f2e8c6ccc9..99fbc2f238c4 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -56,6 +56,38 @@ int sg_nents(struct scatterlist *sg)
56} 56}
57EXPORT_SYMBOL(sg_nents); 57EXPORT_SYMBOL(sg_nents);
58 58
59/**
60 * sg_nents_for_len - return total count of entries in scatterlist
61 * needed to satisfy the supplied length
62 * @sg: The scatterlist
63 * @len: The total required length
64 *
65 * Description:
66 * Determines the number of entries in sg that are required to meet
67 * the supplied length, taking into acount chaining as well
68 *
69 * Returns:
70 * the number of sg entries needed, negative error on failure
71 *
72 **/
73int sg_nents_for_len(struct scatterlist *sg, u64 len)
74{
75 int nents;
76 u64 total;
77
78 if (!len)
79 return 0;
80
81 for (nents = 0, total = 0; sg; sg = sg_next(sg)) {
82 nents++;
83 total += sg->length;
84 if (total >= len)
85 return nents;
86 }
87
88 return -EINVAL;
89}
90EXPORT_SYMBOL(sg_nents_for_len);
59 91
60/** 92/**
61 * sg_last - return the last scatterlist entry in a list 93 * sg_last - return the last scatterlist entry in a list
diff --git a/lib/strnlen_user.c b/lib/strnlen_user.c
index a28df5206d95..3a5f2b366d84 100644
--- a/lib/strnlen_user.c
+++ b/lib/strnlen_user.c
@@ -57,7 +57,8 @@ static inline long do_strnlen_user(const char __user *src, unsigned long count,
57 return res + find_zero(data) + 1 - align; 57 return res + find_zero(data) + 1 - align;
58 } 58 }
59 res += sizeof(unsigned long); 59 res += sizeof(unsigned long);
60 if (unlikely(max < sizeof(unsigned long))) 60 /* We already handled 'unsigned long' bytes. Did we do it all ? */
61 if (unlikely(max <= sizeof(unsigned long)))
61 break; 62 break;
62 max -= sizeof(unsigned long); 63 max -= sizeof(unsigned long);
63 if (unlikely(__get_user(c,(unsigned long __user *)(src+res)))) 64 if (unlikely(__get_user(c,(unsigned long __user *)(src+res))))
@@ -84,13 +85,21 @@ static inline long do_strnlen_user(const char __user *src, unsigned long count,
84 * @str: The string to measure. 85 * @str: The string to measure.
85 * @count: Maximum count (including NUL character) 86 * @count: Maximum count (including NUL character)
86 * 87 *
87 * Context: User context only. This function may sleep. 88 * Context: User context only. This function may sleep if pagefaults are
89 * enabled.
88 * 90 *
89 * Get the size of a NUL-terminated string in user space. 91 * Get the size of a NUL-terminated string in user space.
90 * 92 *
91 * Returns the size of the string INCLUDING the terminating NUL. 93 * Returns the size of the string INCLUDING the terminating NUL.
92 * If the string is too long, returns 'count+1'. 94 * If the string is too long, returns a number larger than @count. User
95 * has to check the return value against "> count".
93 * On exception (or invalid count), returns 0. 96 * On exception (or invalid count), returns 0.
97 *
98 * NOTE! You should basically never use this function. There is
99 * almost never any valid case for using the length of a user space
100 * string, since the string can be changed at any time by other
101 * threads. Use "strncpy_from_user()" instead to get a stable copy
102 * of the string.
94 */ 103 */
95long strnlen_user(const char __user *str, long count) 104long strnlen_user(const char __user *str, long count)
96{ 105{
@@ -113,7 +122,8 @@ EXPORT_SYMBOL(strnlen_user);
113 * strlen_user: - Get the size of a user string INCLUDING final NUL. 122 * strlen_user: - Get the size of a user string INCLUDING final NUL.
114 * @str: The string to measure. 123 * @str: The string to measure.
115 * 124 *
116 * Context: User context only. This function may sleep. 125 * Context: User context only. This function may sleep if pagefaults are
126 * enabled.
117 * 127 *
118 * Get the size of a NUL-terminated string in user space. 128 * Get the size of a NUL-terminated string in user space.
119 * 129 *
diff --git a/lib/swiotlb.c b/lib/swiotlb.c
index 4abda074ea45..42e192decbfd 100644
--- a/lib/swiotlb.c
+++ b/lib/swiotlb.c
@@ -537,8 +537,9 @@ EXPORT_SYMBOL_GPL(swiotlb_tbl_map_single);
537 * Allocates bounce buffer and returns its kernel virtual address. 537 * Allocates bounce buffer and returns its kernel virtual address.
538 */ 538 */
539 539
540phys_addr_t map_single(struct device *hwdev, phys_addr_t phys, size_t size, 540static phys_addr_t
541 enum dma_data_direction dir) 541map_single(struct device *hwdev, phys_addr_t phys, size_t size,
542 enum dma_data_direction dir)
542{ 543{
543 dma_addr_t start_dma_addr = phys_to_dma(hwdev, io_tlb_start); 544 dma_addr_t start_dma_addr = phys_to_dma(hwdev, io_tlb_start);
544 545
@@ -655,7 +656,7 @@ swiotlb_alloc_coherent(struct device *hwdev, size_t size,
655 */ 656 */
656 phys_addr_t paddr = map_single(hwdev, 0, size, DMA_FROM_DEVICE); 657 phys_addr_t paddr = map_single(hwdev, 0, size, DMA_FROM_DEVICE);
657 if (paddr == SWIOTLB_MAP_ERROR) 658 if (paddr == SWIOTLB_MAP_ERROR)
658 return NULL; 659 goto err_warn;
659 660
660 ret = phys_to_virt(paddr); 661 ret = phys_to_virt(paddr);
661 dev_addr = phys_to_dma(hwdev, paddr); 662 dev_addr = phys_to_dma(hwdev, paddr);
@@ -669,7 +670,7 @@ swiotlb_alloc_coherent(struct device *hwdev, size_t size,
669 /* DMA_TO_DEVICE to avoid memcpy in unmap_single */ 670 /* DMA_TO_DEVICE to avoid memcpy in unmap_single */
670 swiotlb_tbl_unmap_single(hwdev, paddr, 671 swiotlb_tbl_unmap_single(hwdev, paddr,
671 size, DMA_TO_DEVICE); 672 size, DMA_TO_DEVICE);
672 return NULL; 673 goto err_warn;
673 } 674 }
674 } 675 }
675 676
@@ -677,6 +678,13 @@ swiotlb_alloc_coherent(struct device *hwdev, size_t size,
677 memset(ret, 0, size); 678 memset(ret, 0, size);
678 679
679 return ret; 680 return ret;
681
682err_warn:
683 pr_warn("swiotlb: coherent allocation failed for device %s size=%zu\n",
684 dev_name(hwdev), size);
685 dump_stack();
686
687 return NULL;
680} 688}
681EXPORT_SYMBOL(swiotlb_alloc_coherent); 689EXPORT_SYMBOL(swiotlb_alloc_coherent);
682 690
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index a382e4a32609..782ae8ca2c06 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -36,7 +36,7 @@
36 * Adds the timer node to the timerqueue, sorted by the 36 * Adds the timer node to the timerqueue, sorted by the
37 * node's expires value. 37 * node's expires value.
38 */ 38 */
39void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 39bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
40{ 40{
41 struct rb_node **p = &head->head.rb_node; 41 struct rb_node **p = &head->head.rb_node;
42 struct rb_node *parent = NULL; 42 struct rb_node *parent = NULL;
@@ -56,8 +56,11 @@ void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
56 rb_link_node(&node->node, parent, p); 56 rb_link_node(&node->node, parent, p);
57 rb_insert_color(&node->node, &head->head); 57 rb_insert_color(&node->node, &head->head);
58 58
59 if (!head->next || node->expires.tv64 < head->next->expires.tv64) 59 if (!head->next || node->expires.tv64 < head->next->expires.tv64) {
60 head->next = node; 60 head->next = node;
61 return true;
62 }
63 return false;
61} 64}
62EXPORT_SYMBOL_GPL(timerqueue_add); 65EXPORT_SYMBOL_GPL(timerqueue_add);
63 66
@@ -69,7 +72,7 @@ EXPORT_SYMBOL_GPL(timerqueue_add);
69 * 72 *
70 * Removes the timer node from the timerqueue. 73 * Removes the timer node from the timerqueue.
71 */ 74 */
72void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 75bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
73{ 76{
74 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 77 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
75 78
@@ -82,6 +85,7 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
82 } 85 }
83 rb_erase(&node->node, &head->head); 86 rb_erase(&node->node, &head->head);
84 RB_CLEAR_NODE(&node->node); 87 RB_CLEAR_NODE(&node->node);
88 return head->next != NULL;
85} 89}
86EXPORT_SYMBOL_GPL(timerqueue_del); 90EXPORT_SYMBOL_GPL(timerqueue_del);
87 91
generated by cgit v1.2.2 (git 2.25.0) at 2025-12-26 15:31:47 -0500