On Tue, Mar 01, 2011 at 05:37:49PM -0600, Amit Kulkarni wrote:
> I found 2 possible null pointers by clang static analyzer and I have
> attached it to email later. I was also reading the code in this file
> and I found out that
>
> 1) most of the time in uvm_pmr_getpages(), a newly inserted printf at
> line 792 is never reached. I put that printf just to check and verify
> a clang warning that search[] is uninitialized. Almost all page
> allocations during boot and seen in dmesg are happening in either on
> line 786 or line 789 in
>
> if (maxseg == 1 || count == 1)
> and
> else if (maxseg >= count && (flags & UVM_PLA_TRYCONTIG) == 0) {
>
> So is that else {} block not being reached and is redundant?
It's not redundant.
Consider the case where maxseg > 1, count > 1 and maxseg < count
(for instance maxseg = 2, count = 3).
This rare case will reach the 3rd block.
It being reached rarely is because:
- most allocations are for a single page (uvm_pagealloc)
- most many-page allocations are allocated by a dma controller which
will have maxseg=1 or maxseg=count only.
> It looks
> like it from the code, as it is only called from uvm_page.c and
> uvm_pglist.c and the if () condition. Is the allocator then spending a
> lot of time in the search[2] case? Or am I crazy to think that
> something's off in that area?
The search[2] case is more pessimistic and slower than the search[1]
case, which in turn is more pessimistic and slower than the search[0]
case.
However, the slower cases are optimized out in the different
if-statements.
> 2) another question. Most allocations are either 1 or a power of two.
> But there are a few allocations of 3 pages, specifically most
> allocations are either 1 page, 2 page, some 16's, some 32's, one
> single 128. I printed this info by checking for value of search[try]
> at label rescan: on line 901 in uvm_pmemrange.c
>
> Would this cause fragmentation or misalignment and ultimately a
> problem?
Fragmentation is filled out aggressively. Suppose the 3-page allocation
came from a range that contained 5 pages, then the 2 remaining pages
(which may or may not be contiguous) will be quickly handed out to an
allocation that will be fine with them.
Or more formally:
- each free space consists of a contig range of pages, where no 2 free
spaces will exist that "connect",
- the free spaces are kept in a set, sorted on their size,
- every allocation will be fulfilled using the first elements that do
not violate the allocation constraints.
However, you can check the current level of fragmentation by dropping in
ddb:
call uvm_pmr_print()
-- output on my laptop --
Ranges, use queue:
* [0x1000-0x100000] use=1 nsegs=2514 maxsegsz[0]=0x6a7d0 maxsegsz[1]=0x0
free=0xde66e
* [0x0-0x1000] use=2 nsegs=5 maxsegsz[0]=0x45c maxsegsz[1]=0x0
free=0xa66
#ranges = 2
--
The nsegs value shows how many segments are available, while the
maxsegsz describes the size of the largest segment, i.e. the largest
contig allocation that is possible.
In this case, 0x6a7d0 pages (1.7GB) contig memory is available.
(Hex numbers are page counts, so need to be multiplied by pagesize.)
> There were exactly eight 3 page allocations after bios got
> handed control to /bsd immediately after the lines
>
> real mem = 8587771904 (8189MB)
> avail mem = 8345174016 (7958MB)
>
> and a single 3 page allocation after mtrr:Pentium Pro MTRR support. I
> get a usb_allocmem() issue right after this line on a NVIDIA USB EHCI
> controller on this Sun Ultra 40 with NVIDIA everything. I am attaching
> a dmesg also. I have to keep the ehci commented in GENERIC to get it
> to boot or disable ehci in UKC everytime.
>
> Would this single odd 3 page alloc cause a problem? Or am I crazy to
> think it should?
Shouldn't be a problem.
> Thanks for your time,
> amit
>
> clang reports for the null pointers
>
> https://filestogeaux.lsu.edu/public/download.php?FILE=akulka1/20861LJ6oU4
> https://filestogeaux.lsu.edu/public/download.php?FILE=akulka1/32877HWMeIq
> https://filestogeaux.lsu.edu/public/download.php?FILE=akulka1/12907BUBXhj
>
>
> Index: uvm_pmemrange.c
> ===================================================================
> RCS file: /cvs/src/sys/uvm/uvm_pmemrange.c,v
> retrieving revision 1.18
> diff -u -i uvm_pmemrange.c
> --- uvm_pmemrange.c 28 Aug 2010 22:27:47 -0000 1.18
> +++ uvm_pmemrange.c 1 Mar 2011 22:28:46 -0000
> @@ -634,7 +634,7 @@
> * uvm_page_init() may not have initialized its array sorted by
> * page number.
> */
> - for (iter = start; iter != end; iter = iter_end) {
> + for (iter = start; iter != NULL && iter != end; iter = iter_end) {
end is guaranteed to be either NULL or between iter and end of the list.
Therefor this is not a null pointer error.
> iter_end = TAILQ_NEXT(iter, pageq);
> TAILQ_REMOVE(pgl, iter, pageq);
> }
> @@ -1628,7 +1628,7 @@
> * Ack, no hits. Walk the address tree until to find something usable.
> */
> for (low = RB_NEXT(uvm_pmr_addr, &pmr->addr, low);
> - low != high;
> + low != high && high_next != NULL;
> low = RB_NEXT(uvm_pmr_addr, &pmr->addr, low)) {
> KASSERT(PMR_IS_SUBRANGE_OF(atop(VM_PAGE_TO_PHYS(high_next)),
> atop(VM_PAGE_TO_PHYS(high_next)) + high_next->fpgsz,
This could be a null pointer. But your fix is wrong.
Looking at the code, it seems very weird to repeatedly test high_next in
the loop, while it is neither modified nor used during or after the
loop. I think it needs to be low (which is used in the iteration) instead
of high_next.
I'll look more into this tonight.
Thanks for the report.
Ciao,
--
Ariane
