Bug Summary

File:src/usr.bin/less/less/../linenum.c
Warning:line 197, column 23
Access to field 'prev' results in a dereference of a null pointer (loaded from variable 'spare')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name linenum.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.bin/less/less/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.bin/less/less/.. -D SYSDIR="/etc" -D HELPDIR="/usr/share/misc" -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.bin/less/less/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.bin/less/less/../linenum.c
1/*
2 * Copyright (C) 1984-2012 Mark Nudelman
3 * Modified for use with illumos by Garrett D'Amore.
4 * Copyright 2014 Garrett D'Amore <garrett@damore.org>
5 *
6 * You may distribute under the terms of either the GNU General Public
7 * License or the Less License, as specified in the README file.
8 *
9 * For more information, see the README file.
10 */
11
12/*
13 * Code to handle displaying line numbers.
14 *
15 * Finding the line number of a given file position is rather tricky.
16 * We don't want to just start at the beginning of the file and
17 * count newlines, because that is slow for large files (and also
18 * wouldn't work if we couldn't get to the start of the file; e.g.
19 * if input is a long pipe).
20 *
21 * So we use the function add_lnum to cache line numbers.
22 * We try to be very clever and keep only the more interesting
23 * line numbers when we run out of space in our table. A line
24 * number is more interesting than another when it is far from
25 * other line numbers. For example, we'd rather keep lines
26 * 100,200,300 than 100,101,300. 200 is more interesting than
27 * 101 because 101 can be derived very cheaply from 100, while
28 * 200 is more expensive to derive from 100.
29 *
30 * The function currline() returns the line number of a given
31 * position in the file. As a side effect, it calls add_lnum
32 * to cache the line number. Therefore currline is occasionally
33 * called to make sure we cache line numbers often enough.
34 */
35
36#include <sys/time.h>
37
38#include <time.h>
39
40#include "less.h"
41
42/*
43 * Structure to keep track of a line number and the associated file position.
44 * A doubly-linked circular list of line numbers is kept ordered by line number.
45 */
46struct linenum_info {
47 struct linenum_info *next; /* Link to next in the list */
48 struct linenum_info *prev; /* Line to previous in the list */
49 off_t pos; /* File position */
50 off_t gap; /* Gap between prev and next */
51 off_t line; /* Line number */
52};
53/*
54 * "gap" needs some explanation: the gap of any particular line number
55 * is the distance between the previous one and the next one in the list.
56 * ("Distance" means difference in file position.) In other words, the
57 * gap of a line number is the gap which would be introduced if this
58 * line number were deleted. It is used to decide which one to replace
59 * when we have a new one to insert and the table is full.
60 */
61
62#define NPOOL200 200 /* Size of line number pool */
63
64#define LONGTIME(2) (2) /* In seconds */
65
66static struct linenum_info anchor; /* Anchor of the list */
67static struct linenum_info *freelist; /* Anchor of the unused entries */
68static struct linenum_info pool[NPOOL200]; /* The pool itself */
69static struct linenum_info *spare; /* We always keep one spare entry */
70
71extern int linenums;
72extern int sc_height;
73extern int screen_trashed;
74
75/*
76 * Initialize the line number structures.
77 */
78void
79clr_linenum(void)
80{
81 struct linenum_info *p;
82
83 /*
84 * Put all the entries on the free list.
85 * Leave one for the "spare".
86 */
87 for (p = pool; p < &pool[NPOOL200-2]; p++)
88 p->next = p+1;
89 pool[NPOOL200-2].next = NULL((void *)0);
90 freelist = pool;
91
92 spare = &pool[NPOOL200-1];
93
94 /*
95 * Initialize the anchor.
96 */
97 anchor.next = anchor.prev = &anchor;
98 anchor.gap = 0;
99 anchor.pos = 0;
100 anchor.line = 1;
101}
102
103/*
104 * Calculate the gap for an entry.
105 */
106static void
107calcgap(struct linenum_info *p)
108{
109 /*
110 * Don't bother to compute a gap for the anchor.
111 * Also don't compute a gap for the last one in the list.
112 * The gap for that last one should be considered infinite,
113 * but we never look at it anyway.
114 */
115 if (p == &anchor || p->next == &anchor)
116 return;
117 p->gap = p->next->pos - p->prev->pos;
118}
119
120/*
121 * Add a new line number to the cache.
122 * The specified position (pos) should be the file position of the
123 * FIRST character in the specified line.
124 */
125void
126add_lnum(off_t linenum, off_t pos)
127{
128 struct linenum_info *p;
129 struct linenum_info *new;
130 struct linenum_info *nextp;
131 struct linenum_info *prevp;
132 off_t mingap;
133
134 /*
135 * Find the proper place in the list for the new one.
136 * The entries are sorted by position.
137 */
138 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
18
←
Assuming the condition is false
→
139 if (p->line == linenum)
140 /* We already have this one. */
141 return;
142 nextp = p;
143 prevp = p->prev;
144
145 if (freelist != NULL((void *)0)) {
19
←
Assuming 'freelist' is equal to NULL
→
20
←
Taking false branch
→
146 /*
147 * We still have free (unused) entries.
148 * Use one of them.
149 */
150 new = freelist;
151 freelist = freelist->next;
152 } else {
153 /*
154 * No free entries.
155 * Use the "spare" entry.
156 */
157 new = spare;
158 spare = NULL((void *)0);
21
←
Null pointer value stored to 'spare'
→
159 }
160
161 /*
162 * Fill in the fields of the new entry,
163 * and insert it into the proper place in the list.
164 */
165 new->next = nextp;
166 new->prev = prevp;
167 new->pos = pos;
168 new->line = linenum;
169
170 nextp->prev = new;
171 prevp->next = new;
172
173 /*
174 * Recalculate gaps for the new entry and the neighboring entries.
175 */
176 calcgap(new);
177 calcgap(nextp);
178 calcgap(prevp);
179
180 if (spare
21.1
'spare' is equal to NULL
 == NULL((void *)0)) {
22
←
Taking true branch
→
181 /*
182 * We have used the spare entry.
183 * Scan the list to find the one with the smallest
184 * gap, take it out and make it the spare.
185 * We should never remove the last one, so stop when
186 * we get to p->next == &anchor. This also avoids
187 * looking at the gap of the last one, which is
188 * not computed by calcgap.
189 */
190 mingap = anchor.next->gap;
191 for (p = anchor.next; p->next != &anchor; p = p->next) {
23
←
Loop condition is false. Execution continues on line 197
→
192 if (p->gap <= mingap) {
193 spare = p;
194 mingap = p->gap;
195 }
196 }
197 spare->next->prev = spare->prev;
24
←
Access to field 'prev' results in a dereference of a null pointer (loaded from variable 'spare')
198 spare->prev->next = spare->next;
199 }
200}
201
202static int loopcount;
203static struct timespec timeout;
204
205static void
206timeout_set(int seconds)
207{
208 clock_gettime(CLOCK_MONOTONIC3, &timeout);
209 timeout.tv_sec += seconds;
210}
211
212static int
213timeout_elapsed(void)
214{
215 struct timespec now;
216
217 clock_gettime(CLOCK_MONOTONIC3, &now);
218 return timespeccmp(&now, &timeout, >=)(((&now)->tv_sec == (&timeout)->tv_sec) ? ((&
now)->tv_nsec >= (&timeout)->tv_nsec) : ((&now
)->tv_sec >= (&timeout)->tv_sec));
219}
220
221static void
222longish(void)
223{
224 if (loopcount >= 0 && ++loopcount > 100) {
225 loopcount = 0;
226 if (timeout_elapsed()) {
227 ierror("Calculating line numbers", NULL((void *)0));
228 loopcount = -1;
229 }
230 }
231}
232
233/*
234 * Turn off line numbers because the user has interrupted
235 * a lengthy line number calculation.
236 */
237static void
238abort_long(void)
239{
240 if (linenums == OPT_ONPLUS2)
241 /*
242 * We were displaying line numbers, so need to repaint.
243 */
244 screen_trashed = 1;
245 linenums = 0;
246 error("Line numbers turned off", NULL((void *)0));
247}
248
249/*
250 * Find the line number associated with a given position.
251 * Return 0 if we can't figure it out.
252 */
253off_t
254find_linenum(off_t pos)
255{
256 struct linenum_info *p;
257 off_t linenum;
258 off_t cpos;
259
260 if (!linenums)
4
←
Assuming 'linenums' is not equal to 0
→
5
←
Taking false branch
→
261 /*
262 * We're not using line numbers.
263 */
264 return (0);
265 if (pos == -1)
6
←
Taking false branch
→
266 /*
267 * Caller doesn't know what he's talking about.
268 */
269 return (0);
270 if (pos <= ch_zero()(0))
7
←
Assuming 'pos' is > ch_zero()
→
8
←
Taking false branch
→
271 /*
272 * Beginning of file is always line number 1.
273 */
274 return (1);
275
276 /*
277 * Find the entry nearest to the position we want.
278 */
279 for (p = anchor.next; p != &anchor && p->pos < pos; p = p->next)
9
←
Assuming the condition is false
→
280 continue;
281 if (p->pos == pos)
10
←
Assuming 'pos' is not equal to field 'pos'
→
11
←
Taking false branch
→
282 /* Found it exactly. */
283 return (p->line);
284
285 /*
286 * This is the (possibly) time-consuming part.
287 * We start at the line we just found and start
288 * reading the file forward or backward till we
289 * get to the place we want.
290 *
291 * First decide whether we should go forward from the
292 * previous one or backwards from the next one.
293 * The decision is based on which way involves
294 * traversing fewer bytes in the file.
295 */
296 timeout_set(LONGTIME(2));
297 if (p == &anchor || pos - p->prev->pos < p->pos - pos) {
12
←
Assuming the condition is true
→
298 /*
299 * Go forward.
300 */
301 p = p->prev;
302 if (ch_seek(p->pos))
13
←
Assuming the condition is false
→
14
←
Taking false branch
→
303 return (0);
304 loopcount = 0;
305 for (linenum = p->line, cpos = p->pos; cpos < pos; linenum++) {
15
←
Assuming 'cpos' is >= 'pos'
→
16
←
Loop condition is false. Execution continues on line 321
→
306 /*
307 * Allow a signal to abort this loop.
308 */
309 cpos = forw_raw_line(cpos, NULL((void *)0), NULL((void *)0));
310 if (abort_sigs()) {
311 abort_long();
312 return (0);
313 }
314 if (cpos == -1)
315 return (0);
316 longish();
317 }
318 /*
319 * We might as well cache it.
320 */
321 add_lnum(linenum, cpos);
17
←
Calling 'add_lnum'
→
322 /*
323 * If the given position is not at the start of a line,
324 * make sure we return the correct line number.
325 */
326 if (cpos > pos)
327 linenum--;
328 } else {
329 /*
330 * Go backward.
331 */
332 if (ch_seek(p->pos))
333 return (0);
334 loopcount = 0;
335 for (linenum = p->line, cpos = p->pos; cpos > pos; linenum--) {
336 /*
337 * Allow a signal to abort this loop.
338 */
339 cpos = back_raw_line(cpos, NULL((void *)0), NULL((void *)0));
340 if (abort_sigs()) {
341 abort_long();
342 return (0);
343 }
344 if (cpos == -1)
345 return (0);
346 longish();
347 }
348 /*
349 * We might as well cache it.
350 */
351 add_lnum(linenum, cpos);
352 }
353
354 return (linenum);
355}
356
357/*
358 * Find the position of a given line number.
359 * Return -1 if we can't figure it out.
360 */
361off_t
362find_pos(off_t linenum)
363{
364 struct linenum_info *p;
365 off_t cpos;
366 off_t clinenum;
367
368 if (linenum <= 1)
369 /*
370 * Line number 1 is beginning of file.
371 */
372 return (ch_zero()(0));
373
374 /*
375 * Find the entry nearest to the line number we want.
376 */
377 for (p = anchor.next; p != &anchor && p->line < linenum; p = p->next)
378 continue;
379 if (p->line == linenum)
380 /* Found it exactly. */
381 return (p->pos);
382
383 if (p == &anchor || linenum - p->prev->line < p->line - linenum) {
384 /*
385 * Go forward.
386 */
387 p = p->prev;
388 if (ch_seek(p->pos))
389 return (-1);
390 for (clinenum = p->line, cpos = p->pos;
391 clinenum < linenum;
392 clinenum++) {
393 /*
394 * Allow a signal to abort this loop.
395 */
396 cpos = forw_raw_line(cpos, NULL((void *)0), NULL((void *)0));
397 if (abort_sigs())
398 return (-1);
399 if (cpos == -1)
400 return (-1);
401 }
402 } else {
403 /*
404 * Go backward.
405 */
406 if (ch_seek(p->pos))
407 return (-1);
408 for (clinenum = p->line, cpos = p->pos;
409 clinenum > linenum;
410 clinenum--) {
411 /*
412 * Allow a signal to abort this loop.
413 */
414 cpos = back_raw_line(cpos, (char **)NULL((void *)0), (int *)NULL((void *)0));
415 if (abort_sigs())
416 return (-1);
417 if (cpos == -1)
418 return (-1);
419 }
420 }
421 /*
422 * We might as well cache it.
423 */
424 add_lnum(clinenum, cpos);
425 return (cpos);
426}
427
428/*
429 * Return the line number of the "current" line.
430 * The argument "where" tells which line is to be considered
431 * the "current" line (e.g. TOP, BOTTOM, MIDDLE, etc).
432 */
433off_t
434currline(int where)
435{
436 off_t pos;
437 off_t len;
438 off_t linenum;
439
440 pos = position(where);
441 len = ch_length();
442 while (pos == -1 && where >= 0 && where < sc_height)
1
Assuming the condition is false
→
443 pos = position(++where);
444 if (pos == -1)
2
←
Taking false branch
→
445 pos = len;
446 linenum = find_linenum(pos);
3
←
Calling 'find_linenum'
→
447 if (pos == len)
448 linenum--;
449 return (linenum);
450}