1 /*
2 * Copyright (c) 2014-2020 Douglas Gilbert.
3 * All rights reserved.
4 * Use of this source code is governed by a BSD-style
5 * license that can be found in the BSD_LICENSE file.
6 *
7 * SPDX-License-Identifier: BSD-2-Clause
8 *
9 * Version 1.02 [20201124]
10 */
11
12 // C headers
13 #include <stdio.h>
14 #include <stdint.h>
15 #include <string.h>
16 #include <limits.h>
17 #include <ctype.h>
18 #include <errno.h>
19 #define __STDC_FORMAT_MACROS 1
20 #include <inttypes.h>
21
22 // C++ headers
23 #include <array>
24
25 #include "sg_scat_gath.h"
26 #include "sg_lib.h"
27 #include "sg_pr2serr.h"
28
29 using namespace std;
30
31 #define MAX_SGL_NUM_VAL (INT32_MAX - 1) /* should reduce for testing */
32 // #define MAX_SGL_NUM_VAL 7 /* should reduce for testing */
33 #if MAX_SGL_NUM_VAL > INT32_MAX
34 #error "MAX_SGL_NUM_VAL cannot exceed 2^31 - 1"
35 #endif
36
37 bool
empty() const38 scat_gath_list::empty() const
39 {
40 return sgl.empty();
41 }
42
43 bool
empty_or_00() const44 scat_gath_list::empty_or_00() const
45 {
46 if (sgl.empty())
47 return true;
48 return ((sgl.size() == 1) && (sgl[0].lba == 0) && (sgl[0].num == 0));
49 }
50
51 int
num_elems() const52 scat_gath_list::num_elems() const
53 {
54 return sgl.size();
55 }
56
57
58 /* Read numbers (up to 64 bits in size) from command line (comma (or
59 * (single) space **) separated list). Assumed decimal unless prefixed
60 * by '0x', '0X' or contains trailing 'h' or 'H' (which indicate hex).
61 * Returns 0 if ok, or 1 if error. Assumed to be LBA (64 bit) and
62 * number_of_block (32 bit) pairs. ** Space on command line needs to
63 * be escaped, otherwise it is an operand/option separator. */
64 bool
load_from_cli(const char * cl_p,bool b_vb)65 scat_gath_list::load_from_cli(const char * cl_p, bool b_vb)
66 {
67 bool split, full_pair;
68 int in_len, k, j;
69 const int max_nbs = MAX_SGL_NUM_VAL;
70 int64_t ll, large_num;
71 uint64_t prev_lba;
72 char * cp;
73 char * c2p;
74 const char * lcp;
75 class scat_gath_elem sge;
76
77 if (NULL == cl_p) {
78 pr2serr("%s: bad arguments\n", __func__);
79 goto err_out;
80 }
81 lcp = cl_p;
82 in_len = strlen(cl_p);
83 if ('-' == cl_p[0]) { /* read from stdin */
84 pr2serr("%s: logic error: no stdin here\n", __func__);
85 goto err_out;
86 } else { /* list of numbers (default decimal) on command line */
87 k = strspn(cl_p, "0123456789aAbBcCdDeEfFhHxXiIkKmMgGtTpP, ");
88 if (in_len != k) {
89 if (b_vb)
90 pr2serr("%s: error at pos %d\n", __func__, k + 1);
91 goto err_out;
92 }
93 j = 0;
94 full_pair = true;
95 for (k = 0, split = false; ; ++k) {
96 if (split) {
97 /* splitting given elem with large number_of_blocks into
98 * multiple elems within array being built */
99 ++j;
100 sge.lba = prev_lba + (uint64_t)max_nbs;
101 if (large_num > max_nbs) {
102 sge.num = (uint32_t)max_nbs;
103 prev_lba = sge.lba;
104 large_num -= max_nbs;
105 sgl.push_back(sge);
106 } else {
107 sge.num = (uint32_t)large_num;
108 split = false;
109 if (b_vb)
110 pr2serr("%s: split large sg elem into %d element%s\n",
111 __func__, j, (j == 1 ? "" : "s"));
112 sgl.push_back(sge);
113 goto check_for_next;
114 }
115 continue;
116 }
117 full_pair = false;
118 ll = sg_get_llnum(lcp);
119 if (-1 != ll) {
120 sge.lba = (uint64_t)ll;
121 cp = (char *)strchr(lcp, ',');
122 c2p = (char *)strchr(lcp, ' ');
123 if (NULL == cp) {
124 cp = c2p;
125 if (NULL == cp)
126 break;
127 }
128 if (c2p && (c2p < cp))
129 cp = c2p;
130 lcp = cp + 1;
131 } else {
132 if (b_vb)
133 pr2serr("%s: error at pos %d\n", __func__,
134 (int)(lcp - cl_p + 1));
135 goto err_out;
136 }
137 ll = sg_get_llnum(lcp);
138 if (ll >= 0) {
139 full_pair = true;
140 if (ll > max_nbs) {
141 sge.num = (uint32_t)max_nbs;
142 prev_lba = sge.lba;
143 large_num = ll - max_nbs;
144 split = true;
145 j = 1;
146 continue;
147 }
148 sge.num = (uint32_t)ll;
149 } else { /* bad or negative number as number_of_blocks */
150 if (b_vb)
151 pr2serr("%s: bad number at pos %d\n", __func__,
152 (int)(lcp - cl_p + 1));
153 goto err_out;
154 }
155 sgl.push_back(sge);
156 check_for_next:
157 cp = (char *)strchr(lcp, ',');
158 c2p = (char *)strchr(lcp, ' ');
159 if (NULL == cp) {
160 cp = c2p;
161 if (NULL == cp)
162 break;
163 }
164 if (c2p && (c2p < cp))
165 cp = c2p;
166 lcp = cp + 1;
167 } /* end of for loop over items in operand */
168 /* other than first pair, expect even number of items */
169 if ((k > 0) && (! full_pair)) {
170 if (b_vb)
171 pr2serr("%s: expected even number of items: "
172 "LBA0,NUM0,LBA1,NUM1...\n", __func__);
173 goto err_out;
174 }
175 }
176 return true;
177 err_out:
178 if (0 == m_errno)
179 m_errno = SG_LIB_SYNTAX_ERROR;
180 return false;
181 }
182
183 bool
file2sgl_helper(FILE * fp,const char * fnp,bool def_hex,bool flexible,bool b_vb)184 scat_gath_list::file2sgl_helper(FILE * fp, const char * fnp, bool def_hex,
185 bool flexible, bool b_vb)
186 {
187 bool bit0;
188 bool pre_addr1 = true;
189 bool pre_hex_seen = false;
190 int in_len, k, j, m, ind;
191 const int max_nbs = MAX_SGL_NUM_VAL;
192 int off = 0;
193 int64_t ll;
194 uint64_t ull, prev_lba;
195 char * lcp;
196 class scat_gath_elem sge;
197 char line[1024];
198
199 for (j = 0 ; ; ++j) {
200 if (NULL == fgets(line, sizeof(line), fp))
201 break;
202 // could improve with carry_over logic if sizeof(line) too small
203 in_len = strlen(line);
204 if (in_len > 0) {
205 if ('\n' == line[in_len - 1]) {
206 --in_len;
207 line[in_len] = '\0';
208 } else {
209 m_errno = SG_LIB_SYNTAX_ERROR;
210 if (b_vb)
211 pr2serr("%s: %s: line too long, max %d bytes\n",
212 __func__, fnp, (int)(sizeof(line) - 1));
213 goto err_out;
214 }
215 }
216 if (in_len < 1)
217 continue;
218 lcp = line;
219 m = strspn(lcp, " \t");
220 if (m == in_len)
221 continue;
222 lcp += m;
223 in_len -= m;
224 if ('#' == *lcp)
225 continue;
226 if (pre_addr1 || pre_hex_seen) {
227 /* Accept lines with leading 'HEX' and ignore as long as there
228 * is one _before_ any LBA,NUM lines in the file. This allows
229 * HEX marked sgls to be concaternated together. */
230 if (('H' == toupper(lcp[0])) && ('E' == toupper(lcp[1])) &&
231 ('X' == toupper(lcp[2]))) {
232 pre_hex_seen = true;
233 if (def_hex)
234 continue; /* bypass 'HEX' marker line if expecting hex */
235 else {
236 if (flexible) {
237 def_hex = true; /* okay, switch to hex parse */
238 continue;
239 } else {
240 pr2serr("%s: %s: 'hex' string detected on line %d, "
241 "expecting decimal\n", __func__, fnp, j + 1);
242 m_errno = EINVAL;
243 goto err_out;
244 }
245 }
246 }
247 }
248 k = strspn(lcp, "0123456789aAbBcCdDeEfFhHxXbBdDiIkKmMgGtTpP, \t");
249 if ((k < in_len) && ('#' != lcp[k])) {
250 m_errno = EINVAL;
251 if (b_vb)
252 pr2serr("%s: %s: syntax error at line %d, pos %d\n",
253 __func__, fnp, j + 1, m + k + 1);
254 goto err_out;
255 }
256 for (k = 0; k < 256; ++k) {
257 /* limit parseable items on one line to 256 */
258 if (def_hex) { /* don't accept negatives or multipliers */
259 if (1 == sscanf(lcp, "%" SCNx64, &ull))
260 ll = (int64_t)ull;
261 else
262 ll = -1; /* use (2**64 - 1) as error flag */
263 } else
264 ll = sg_get_llnum(lcp);
265 if (-1 != ll) {
266 ind = ((off + k) >> 1);
267 bit0 = !! (0x1 & (off + k));
268 if (ind >= SG_SGL_MAX_ELEMENTS) {
269 m_errno = EINVAL;
270 if (b_vb)
271 pr2serr("%s: %s: array length exceeded\n", __func__,
272 fnp);
273 goto err_out;
274 }
275 if (bit0) { /* bit0 set when decoding a NUM */
276 if (ll < 0) {
277 m_errno = EINVAL;
278 if (b_vb)
279 pr2serr("%s: %s: bad number in line %d, at pos "
280 "%d\n", __func__, fnp, j + 1,
281 (int)(lcp - line + 1));
282 goto err_out;
283 }
284 if (ll > max_nbs) {
285 int h = 1;
286
287 /* split up this elem into multiple, smaller elems */
288 do {
289 sge.num = (uint32_t)max_nbs;
290 prev_lba = sge.lba;
291 sgl.push_back(sge);
292 sge.lba = prev_lba + (uint64_t)max_nbs;
293 ++h;
294 off += 2;
295 ll -= max_nbs;
296 } while (ll > max_nbs);
297 if (b_vb)
298 pr2serr("%s: split large sg elem into %d "
299 "elements\n", __func__, h);
300 }
301 sge.num = (uint32_t)ll;
302 sgl.push_back(sge);
303 } else { /* bit0 clear when decoding a LBA */
304 if (pre_addr1)
305 pre_addr1 = false;
306 sge.lba = (uint64_t)ll;
307 }
308 } else { /* failed to decode number on line */
309 if ('#' == *lcp) { /* numbers before #, rest of line comment */
310 --k;
311 break; /* goes to next line */
312 }
313 m_errno = EINVAL;
314 if (b_vb)
315 pr2serr("%s: %s: error in line %d, at pos %d\n",
316 __func__, fnp, j + 1, (int)(lcp - line + 1));
317 goto err_out;
318 }
319 lcp = strpbrk(lcp, " ,\t#");
320 if ((NULL == lcp) || ('#' == *lcp))
321 break;
322 lcp += strspn(lcp, " ,\t");
323 if ('\0' == *lcp)
324 break;
325 } /* <<< end of for(k < 256) loop */
326 off += (k + 1);
327 } /* <<< end of for loop, one iteration per line */
328 /* allow one items, but not higher odd number of items */
329 if ((off > 1) && (0x1 & off)) {
330 m_errno = EINVAL;
331 if (b_vb)
332 pr2serr("%s: %s: expect even number of items: "
333 "LBA0,NUM0,LBA1,NUM1...\n", __func__, fnp);
334 goto err_out;
335 }
336 clearerr(fp); /* even EOF on first pass needs this before rescan */
337 return true;
338 err_out:
339 clearerr(fp);
340 return false;
341 }
342
343 /* Read numbers from filename (or stdin), line by line (comma (or (single)
344 * space) separated list); places starting_LBA,number_of_block pairs in an
345 * array of scat_gath_elem elements pointed to by the returned value. If
346 * this fails NULL is returned and an error number is written to errp (if it
347 * is non-NULL). Assumed decimal (and may have suffix multipliers) when
348 * def_hex==false; if a number is prefixed by '0x', '0X' or contains trailing
349 * 'h' or 'H' that denotes a hex number. When def_hex==true all numbers are
350 * assumed to be hex (ignored '0x' prefixes and 'h' suffixes) and multipliers
351 * are not permitted. Heap allocates an array just big enough to hold all
352 * elements if the file is countable. Pipes and stdin are not considered
353 * countable. In the non-countable case an array of MAX_FIXED_SGL_ELEMS
354 * elements is pre-allocated; if it is exceeded sg_convert_errno(EDOM) is
355 * placed in *errp (if it is non-NULL). One of the first actions is to write
356 * 0 to *errp (if it is non-NULL) so the caller does not need to zero it
357 * before calling. */
358 bool
load_from_file(const char * file_name,bool def_hex,bool flexible,bool b_vb)359 scat_gath_list::load_from_file(const char * file_name, bool def_hex,
360 bool flexible, bool b_vb)
361 {
362 bool have_stdin;
363 bool have_err = false;
364 FILE * fp;
365 const char * fnp;
366
367 have_stdin = ((1 == strlen(file_name)) && ('-' == file_name[0]));
368 if (have_stdin) {
369 fp = stdin;
370 fnp = "<stdin>";
371 } else {
372 fnp = file_name;
373 fp = fopen(fnp, "r");
374 if (NULL == fp) {
375 m_errno = errno;
376 if (b_vb)
377 pr2serr("%s: opening %s: %s\n", __func__, fnp,
378 safe_strerror(m_errno));
379 return false;
380 }
381 }
382 if (! file2sgl_helper(fp, fnp, def_hex, flexible, b_vb))
383 have_err = true;
384 if (! have_stdin)
385 fclose(fp);
386 return have_err ? false : true;
387 }
388
389 const char *
linearity_as_str() const390 scat_gath_list::linearity_as_str() const
391 {
392 switch (linearity) {
393 case SGL_LINEAR:
394 return "linear";
395 case SGL_MONOTONIC:
396 return "monotonic";
397 case SGL_MONO_OVERLAP:
398 return "monotonic, overlapping";
399 case SGL_NON_MONOTONIC:
400 return "non-monotonic";
401 default:
402 return "unknown";
403 }
404 }
405
406 void
set_weaker_linearity(enum sgl_linearity_e lin)407 scat_gath_list::set_weaker_linearity(enum sgl_linearity_e lin)
408 {
409 int i_lin = (int)lin;
410
411 if (i_lin > (int)linearity)
412 linearity = lin;
413 }
414
415 /* id_str may be NULL (if so replace by "unknown"), present to enhance verbose
416 * output. */
417 void
dbg_print(bool skip_meta,const char * id_str,bool to_stdout,bool show_sgl) const418 scat_gath_list::dbg_print(bool skip_meta, const char * id_str, bool to_stdout,
419 bool show_sgl) const
420 {
421 int num = sgl.size();
422 const char * caller = id_str ? id_str : "unknown";
423 FILE * fp = to_stdout ? stdout : stderr;
424
425 if (! skip_meta) {
426 fprintf(fp, "%s: elems=%d, sgl %spresent, linearity=%s\n",
427 caller, num, (sgl.empty() ? "not " : ""),
428 linearity_as_str());
429 fprintf(fp, " sum=%" PRId64 ", sum_hard=%s lowest=0x%" PRIx64
430 ", high_lba_p1=", sum, (sum_hard ? "true" : "false"),
431 lowest_lba);
432 fprintf(fp, "0x%" PRIx64 "\n", high_lba_p1);
433 }
434 fprintf(fp, " >> %s scatter gather list (%d element%s):\n", caller, num,
435 (num == 1 ? "" : "s"));
436 if (show_sgl) {
437 int k;
438
439 for (k = 0; k < num; ++k) {
440 const class scat_gath_elem & sge = sgl[k];
441
442 fprintf(fp, " lba: 0x%" PRIx64 ", number: 0x%" PRIx32,
443 sge.lba, sge.num);
444 if (sge.lba > 0)
445 fprintf(fp, " [next lba: 0x%" PRIx64 "]", sge.lba + sge.num);
446 fprintf(fp, "\n");
447 }
448 }
449 }
450
451 /* Assumes sgl array (vector) is setup. The other fields in this object are
452 * set by analyzing sgl in a single pass. The fields that are set are:
453 * fragmented, lowest_lba, high_lba_p1, monotonic, overlapping, sum and
454 * sum_hard. Degenerate elements (i.e. those with 0 blocks) are ignored apart
455 * from when one is last which makes sum_hard false and its LBA becomes
456 * high_lba_p1 if it is the highest in the list. An empty sgl is equivalent
457 * to a 1 element list with [0, 0], so sum_hard==false, monit==true,
458 * fragmented==false and overlapping==false . id_str may be NULL, present
459 * to enhance verbose output. */
460 void
sum_scan(const char * id_str,bool show_sgl,bool b_vb)461 scat_gath_list::sum_scan(const char * id_str, bool show_sgl, bool b_vb)
462 {
463 bool degen = false;
464 bool first = true;
465 bool regular = true; /* no overlapping segments detected */
466 int k;
467 int elems = sgl.size();
468 uint32_t prev_num, t_num;
469 uint64_t prev_lba, t_lba, low, high, end;
470
471 sum = 0;
472 for (k = 0, low = 0, high = 0; k < elems; ++k) {
473 const class scat_gath_elem & sge = sgl[k];
474
475 degen = false;
476 t_num = sge.num;
477 if (0 == t_num) {
478 degen = true;
479 if (! first)
480 continue; /* ignore degen element that not first */
481 }
482 if (first) {
483 low = sge.lba;
484 sum = t_num;
485 high = sge.lba + sge.num;
486 first = false;
487 } else {
488 t_lba = sge.lba;
489 if ((prev_lba + prev_num) != t_lba)
490 set_weaker_linearity(SGL_MONOTONIC);
491 sum += t_num;
492 end = t_lba + t_num;
493 if (end > high)
494 high = end; /* high is one plus highest LBA */
495 if (prev_lba < t_lba)
496 ;
497 else if (prev_lba == t_lba) {
498 if (prev_num > 0) {
499 set_weaker_linearity(SGL_MONO_OVERLAP);
500 break;
501 }
502 } else {
503 low = t_lba;
504 set_weaker_linearity(SGL_NON_MONOTONIC);
505 break;
506 }
507 if (regular) {
508 if ((prev_lba + prev_num) > t_lba)
509 regular = false;
510 }
511 }
512 prev_lba = sge.lba;
513 prev_num = sge.num;
514 } /* end of for loop while still elements and monot true */
515
516 if (k < elems) { /* only here if above breaks are taken */
517 prev_lba = t_lba;
518 ++k;
519 for ( ; k < elems; ++k) {
520 const class scat_gath_elem & sge = sgl[k];
521
522 degen = false;
523 t_lba = sge.lba;
524 t_num = sge.num;
525 if (0 == t_num) {
526 degen = true;
527 continue;
528 }
529 sum += t_num;
530 end = t_lba + t_num;
531 if (end > high)
532 high = end;
533 if (prev_lba > t_lba) {
534 if (t_lba < low)
535 low = t_lba;
536 }
537 prev_lba = t_lba;
538 }
539 } else
540 if (! regular)
541 set_weaker_linearity(SGL_MONO_OVERLAP);
542
543 lowest_lba = low;
544 if (degen && (elems > 0)) { /* last element always impacts high_lba_p1 */
545 t_lba = sgl[elems - 1].lba;
546 high_lba_p1 = (t_lba > high) ? t_lba : high;
547 } else
548 high_lba_p1 = high;
549 sum_hard = (elems > 0) ? ! degen : false;
550 if (b_vb)
551 dbg_print(false, id_str, false, show_sgl);
552 }
553
554 /* Usually will append (or add to start if empty) sge unless 'extra_blks'
555 * exceeds MAX_SGL_NUM_VAL. In that case multiple sge_s are added with
556 * sge.num = MAX_SGL_NUM_VAL or less (for final sge) until extra_blks is
557 * exhausted. Returns new size of scatter gather list. */
558 int
append_1or(int64_t extra_blks,int64_t start_lba)559 scat_gath_list::append_1or(int64_t extra_blks, int64_t start_lba)
560 {
561 int o_num = sgl.size();
562 const int max_nbs = MAX_SGL_NUM_VAL;
563 int64_t cnt = 0;
564 class scat_gath_elem sge;
565
566 if ((extra_blks <= 0) && (start_lba < 0))
567 return o_num; /* nothing to do */
568 if ((o_num > 0) && (! sum_hard)) {
569 sge = sgl[o_num - 1]; /* assume sge.num==0 */
570 if (sge.lba == (uint64_t)start_lba) {
571 if (extra_blks <= max_nbs)
572 sge.num = extra_blks;
573 else
574 sge.num = max_nbs;
575 sgl[o_num - 1] = sge;
576 cnt = sge.num;
577 sum += cnt;
578 sum_hard = true;
579 if (cnt <= extra_blks) {
580 high_lba_p1 = sge.lba + cnt;
581 return o_num;
582 }
583 }
584 } else if (0 == o_num) {
585 lowest_lba = start_lba;
586 if (0 == extra_blks) {
587 sge.lba = start_lba;
588 sge.num = 0;
589 sgl.push_back(sge);
590 high_lba_p1 = sge.lba;
591 return sgl.size();
592 }
593 }
594 for ( ; cnt < extra_blks; cnt += max_nbs) {
595 sge.lba = start_lba + cnt;
596 if ((extra_blks - cnt) <= max_nbs)
597 sge.num = extra_blks - cnt;
598 else
599 sge.num = max_nbs;
600 sgl.push_back(sge);
601 sum += sge.num;
602 } /* always loops at least once */
603 sum_hard = true;
604 high_lba_p1 = sge.lba + sge.num;
605 return sgl.size();
606 }
607
608 int
append_1or(int64_t extra_blks)609 scat_gath_list::append_1or(int64_t extra_blks)
610 {
611 int o_num = sgl.size();
612
613 if (o_num < 1)
614 return append_1or(extra_blks, 0);
615
616 class scat_gath_elem sge = sgl[o_num - 1];
617
618 return append_1or(extra_blks, sge.lba + sge.num);
619 }
620
621 bool
sgls_eq_off(const scat_gath_list & left,int l_e_ind,int l_blk_off,const scat_gath_list & right,int r_e_ind,int r_blk_off,bool allow_partial)622 sgls_eq_off(const scat_gath_list & left, int l_e_ind, int l_blk_off,
623 const scat_gath_list & right, int r_e_ind, int r_blk_off,
624 bool allow_partial)
625 {
626 int lelems = left.sgl.size();
627 int relems = right.sgl.size();
628
629 while ((l_e_ind < lelems) && (r_e_ind < relems)) {
630 if ((left.sgl[l_e_ind].lba + l_blk_off) !=
631 (right.sgl[r_e_ind].lba + r_blk_off))
632 return false;
633
634 int lrem = left.sgl[l_e_ind].num - l_blk_off;
635 int rrem = right.sgl[r_e_ind].num - r_blk_off;
636
637 if (lrem == rrem) {
638 ++l_e_ind;
639 l_blk_off = 0;
640 ++r_e_ind;
641 r_blk_off = 0;
642 } else if (lrem < rrem) {
643 ++l_e_ind;
644 l_blk_off = 0;
645 r_blk_off += lrem;
646 } else {
647 ++r_e_ind;
648 r_blk_off = 0;
649 l_blk_off += rrem;
650 }
651 }
652 if ((l_e_ind >= lelems) && (r_e_ind >= relems))
653 return true;
654 return allow_partial;
655 }
656
657 /* If bad arguments returns -1, otherwise returns the lowest LBA in *sglp .
658 * If no elements considered returns 0. If ignore_degen is true than
659 * ignores all elements with sge.num zero unless always_last is also
660 * true in which case the last element is always considered. */
661 int64_t
get_lowest_lba(bool ignore_degen,bool always_last) const662 scat_gath_list::get_lowest_lba(bool ignore_degen, bool always_last) const
663 {
664 int k;
665 const int num_elems = sgl.size();
666 bool some = (num_elems > 0);
667 int64_t res = INT64_MAX;
668
669 for (k = 0; k < num_elems; ++k) {
670 if ((0 == sgl[k].num) && ignore_degen)
671 continue;
672 if ((int64_t)sgl[k].lba < res)
673 res = sgl[k].lba;
674 }
675 if (always_last && some) {
676 if ((int64_t)sgl[k - 1].lba < res)
677 res = sgl[k - 1].lba;
678 }
679 return (INT64_MAX == res) ? 0 : res;
680 }
681
682 /* Returns >= 0 if sgl can be simplified to a single LBA. So an empty sgl
683 * will return 0; a one element sgl will return its LBA. A multiple element
684 * sgl only returns the first element's LBA (that is not degenerate) if the
685 * sgl is monotonic and not fragmented. In the extreme case takes last
686 * element's LBA if all prior elements are degenerate. Else returns -1 .
687 * Assumes sgl_sum_scan() has been called. */
688 int64_t
get_low_lba_from_linear() const689 scat_gath_list::get_low_lba_from_linear() const
690 {
691 const int num_elems = sgl.size();
692 int k;
693
694 if (num_elems <= 1)
695 return (1 == num_elems) ? sgl[0].lba : 0;
696 else {
697 if (linearity == SGL_LINEAR) {
698 for (k = 0; k < (num_elems - 1); ++k) {
699 if (sgl[k].num > 0)
700 return sgl[k].lba;
701 }
702 /* take last element's LBA if all earlier are degenerate */
703 return sgl[k].lba;
704 } else
705 return -1;
706 }
707 }
708
709 bool
is_pipe_suitable() const710 scat_gath_list::is_pipe_suitable() const
711 {
712 return (lowest_lba == 0) && (linearity == SGL_LINEAR);
713 }
714
scat_gath_iter(const scat_gath_list & parent)715 scat_gath_iter::scat_gath_iter(const scat_gath_list & parent)
716 : sglist(parent), it_el_ind(0), it_blk_off(0), blk_idx(0)
717 {
718 int elems = sglist.num_elems();
719
720 if (elems > 0)
721 extend_last = (0 == sglist.sgl[elems - 1].num);
722 }
723
724 bool
set_by_blk_idx(int64_t _blk_idx)725 scat_gath_iter::set_by_blk_idx(int64_t _blk_idx)
726 {
727 bool first;
728 int k;
729 const int elems = sglist.sgl.size();
730 const int last_ind = elems - 1;
731 int64_t bc = _blk_idx;
732
733 if (bc < 0)
734 return false;
735
736 if (bc == blk_idx)
737 return true;
738 else if (bc > blk_idx) {
739 k = it_el_ind;
740 bc -= blk_idx;
741 } else
742 k = 0;
743 for (first = true; k < elems; ++k, first = false) {
744 uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL :
745 sglist.sgl[k].num;
746 if (first) {
747 if ((int64_t)(num - it_blk_off) < bc)
748 bc -= (num - it_blk_off);
749 else {
750 it_blk_off = bc + it_blk_off;
751 break;
752 }
753 } else {
754 if ((int64_t)num < bc)
755 bc -= num;
756 else {
757 it_blk_off = (uint32_t)bc;
758 break;
759 }
760 }
761 }
762 it_el_ind = k;
763 blk_idx = _blk_idx;
764
765 if (k < elems)
766 return true;
767 else if ((k == elems) && (0 == it_blk_off))
768 return true; /* EOL */
769 else
770 return false;
771 }
772
773 /* Given a blk_count, the iterator (*iter_p) is moved toward the EOL.
774 * Returns true unless blk_count takes iterator two or more past the last
775 * element. So if blk_count takes the iterator to the EOL, this function
776 * returns true. Takes into account iterator's extend_last flag. */
777 bool
add_blks(uint64_t blk_count)778 scat_gath_iter::add_blks(uint64_t blk_count)
779 {
780 bool first;
781 int k;
782 const int elems = sglist.sgl.size();
783 const int last_ind = elems - 1;
784 uint64_t bc = blk_count;
785
786 if (0 == bc)
787 return true;
788 for (first = true, k = it_el_ind; k < elems; ++k) {
789 uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL :
790 sglist.sgl[k].num;
791 if (first) {
792 first = false;
793 if ((uint64_t)(num - it_blk_off) <= bc)
794 bc -= (num - it_blk_off);
795 else {
796 it_blk_off = bc + it_blk_off;
797 break;
798 }
799 } else {
800 if ((uint64_t)num <= bc)
801 bc -= num;
802 else {
803 it_blk_off = (uint32_t)bc;
804 break;
805 }
806 }
807 }
808 it_el_ind = k;
809 blk_idx += blk_count;
810
811 if (k < elems)
812 return true;
813 else if ((k == elems) && (0 == it_blk_off))
814 return true; /* EOL */
815 else
816 return false;
817 }
818
819 /* Move the iterator from its current position (which may be to EOL) towards
820 * the start of the sgl (i.e. backwards) for blk_count blocks. Returns true
821 * if iterator is valid after the move, else returns false. N.B. if false is
822 * returned, then the iterator is invalid and may need to set it to a valid
823 * value. */
824 bool
sub_blks(uint64_t blk_count)825 scat_gath_iter::sub_blks(uint64_t blk_count)
826 {
827 bool first;
828 int k = it_el_ind;
829 uint64_t bc = 0;
830 const uint64_t orig_blk_count = blk_count;
831
832 if (0 == blk_count)
833 return true;
834 for (first = true; k >= 0; --k) {
835 if (first) {
836 if (blk_count > (uint64_t)it_blk_off)
837 blk_count -= it_blk_off;
838 else {
839 it_blk_off -= blk_count;
840 break;
841 }
842 first = false;
843 } else {
844 uint32_t off = sglist.sgl[k].num;
845
846 bc = blk_count;
847 if (bc > (uint64_t)off)
848 blk_count -= off;
849 else {
850 bc = off - bc;
851 break;
852 }
853 }
854 }
855 if (k < 0) {
856 blk_idx = 0;
857 it_blk_off = 0;
858 return false; /* bad situation */
859 }
860 if ((int64_t)orig_blk_count <= blk_idx)
861 blk_idx -= orig_blk_count;
862 else
863 blk_idx = 0;
864 it_el_ind = k;
865 if (! first)
866 it_blk_off = (uint32_t)bc;
867 return true;
868 }
869
870 /* Returns LBA referred to by iterator if valid or returns SG_LBA_INVALID
871 * (-1) if at end or invalid. */
872 int64_t
current_lba() const873 scat_gath_iter::current_lba() const
874 {
875 const int elems = sglist.sgl.size();
876 int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */
877
878 if (it_el_ind < elems) {
879 class scat_gath_elem sge = sglist.sgl[it_el_ind];
880
881 if ((uint32_t)it_blk_off < sge.num)
882 return sge.lba + it_blk_off;
883 else if (((uint32_t)it_blk_off == sge.num) &&
884 ((it_el_ind + 1) < elems)) {
885 class scat_gath_iter iter(*this);
886
887 ++iter.it_el_ind;
888 iter.it_blk_off = 0;
889 /* worst case recursion will stop at end of sgl */
890 return iter.current_lba();
891 }
892 }
893 return res;
894 }
895
896 int64_t
current_lba_rem_num(int & rem_num) const897 scat_gath_iter::current_lba_rem_num(int & rem_num) const
898 {
899 const int elems = sglist.sgl.size();
900 int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */
901
902 if (it_el_ind < elems) {
903 class scat_gath_elem sge = sglist.sgl[it_el_ind];
904
905 if ((uint32_t)it_blk_off < sge.num) {
906 rem_num = sge.num - it_blk_off;
907 return sge.lba + it_blk_off;
908 } else if (((uint32_t)it_blk_off == sge.num) &&
909 ((it_el_ind + 1) < elems)) {
910 class scat_gath_iter iter(*this);
911
912 ++iter.it_el_ind;
913 iter.it_blk_off = 0;
914 /* worst case recursion will stop at end of sgl */
915 return iter.current_lba_rem_num(rem_num);
916 }
917 }
918 rem_num = -1;
919 return res;
920 }
921
922 class scat_gath_elem
current_elem() const923 scat_gath_iter::current_elem() const
924 {
925 const int elems = sglist.sgl.size();
926 class scat_gath_elem sge;
927
928 sge.make_bad();
929 if (it_el_ind < elems)
930 return sglist.sgl[it_el_ind];
931 return sge;
932 }
933
934 /* Returns true of no sgl or sgl is at the end [elems, 0], otherwise it
935 * returns false. */
936 bool
at_end() const937 scat_gath_iter::at_end() const
938 {
939 const int elems = sglist.sgl.size();
940
941 return ((0 == elems) || ((it_el_ind == elems) && (0 == it_blk_off)));
942 }
943
944 /* Returns true if associated iterator is monotonic (increasing) and not
945 * fragmented. Empty sgl and single element degenerate considered linear.
946 * Assumes sgl_sum_scan() has been called on sgl. */
947 bool
is_sgl_linear() const948 scat_gath_iter::is_sgl_linear() const
949 {
950 return sglist.linearity == SGL_LINEAR;
951 }
952
953 /* Should return 1 or more unless max_n<=0 or at_end() */
954 int
linear_for_n_blks(int max_n) const955 scat_gath_iter::linear_for_n_blks(int max_n) const
956 {
957 int k, rem;
958 const int elems = sglist.sgl.size();
959 uint64_t prev_lba;
960 class scat_gath_elem sge;
961
962 if (at_end() || (max_n <= 0))
963 return 0;
964 sge = sglist.sgl[it_el_ind];
965 rem = (int)sge.num - it_blk_off;
966 if (rem <= 0) {
967 sge = sglist.sgl[it_el_ind + 1];
968 rem = (int)sge.num;
969 }
970 if (max_n <= rem)
971 return max_n;
972 prev_lba = sge.lba + sge.num;
973 for (k = it_el_ind + 1; k < elems; ++k) {
974 sge = sglist.sgl[k];
975 if (sge.lba != prev_lba)
976 return rem;
977 rem += sge.num;
978 if (max_n <= rem)
979 return max_n;
980 prev_lba = sge.lba + sge.num;
981 }
982 return rem;
983 }
984
985 /* id_str may be NULL (if so replace by "unknown"), present to enhance verbose
986 * output. */
987 void
dbg_print(const char * id_str,bool to_stdout,int verbose) const988 scat_gath_iter::dbg_print(const char * id_str, bool to_stdout,
989 int verbose) const
990 {
991 const char * caller = id_str ? id_str : "unknown";
992 FILE * fp = to_stdout ? stdout : stderr;
993
994 fprintf(fp, "%s: it_el_ind=%d, it_blk_off=%d, blk_idx=%" PRId64 "\n",
995 caller, it_el_ind, it_blk_off, blk_idx);
996 fprintf(fp, " extend_last=%d\n", extend_last);
997 if (verbose)
998 sglist.dbg_print(false, " iterator's", to_stdout, verbose > 1);
999 }
1000
1001 /* Calculates difference between iterators, logically: res <-- lhs - rhs
1002 * Checks that lhsp and rhsp have same underlying sgl, if not returns
1003 * INT_MIN. Assumes iterators close enough for result to lie in range
1004 * from (-INT_MAX) to INT_MAX (inclusive). */
1005 int
diff_between_iters(const class scat_gath_iter & left,const class scat_gath_iter & right)1006 diff_between_iters(const class scat_gath_iter & left,
1007 const class scat_gath_iter & right)
1008 {
1009 int res, k, r_e_ind, l_e_ind;
1010
1011 if (&left.sglist != &right.sglist) {
1012 pr2serr("%s: bad args\n", __func__);
1013 return INT_MIN;
1014 }
1015 r_e_ind = right.it_el_ind;
1016 l_e_ind = left.it_el_ind;
1017 if (l_e_ind < r_e_ind) { /* so difference will be negative */
1018 res = diff_between_iters(right, left); /* cheat */
1019 if (INT_MIN == res)
1020 return res;
1021 return -res;
1022 } else if (l_e_ind == r_e_ind)
1023 return (int)left.it_blk_off - (int)right.it_blk_off;
1024 /* (l_e_ind > r_e_ind) so (lhs > rhs) */
1025 res = (int)right.sglist.sgl[r_e_ind].num - right.it_blk_off;
1026 for (k = 1; (r_e_ind + k) < l_e_ind; ++k) {
1027 // pr2serr("%s: k=%d, res=%d, num=%d\n", __func__, k, res,
1028 // (int)right.sglist.sgl[r_e_ind + k].num);
1029 res += (int)right.sglist.sgl[r_e_ind + k].num;
1030 }
1031 res += left.it_blk_off;
1032 // pr2serr("%s: at exit res=%d\n", __func__, res);
1033 return res;
1034 }
1035
1036 /* Compares from the current iterator positions of left and left until
1037 * the shorter list is exhausted. Returns false on the first inequality.
1038 * If no inequality and both remaining lists are same length then returns
1039 * true. If no inequality but remaining lists differ in length then returns
1040 * allow_partial. */
1041 bool
sgls_eq_from_iters(const class scat_gath_iter & left,const class scat_gath_iter & right,bool allow_partial)1042 sgls_eq_from_iters(const class scat_gath_iter & left,
1043 const class scat_gath_iter & right,
1044 bool allow_partial)
1045 {
1046 return sgls_eq_off(left.sglist, left.it_el_ind, left.it_blk_off,
1047 right.sglist, right.it_el_ind, right.it_blk_off,
1048 allow_partial);
1049 }
1050