10 ms·

I read the entire thing, and honestly the heap grooming is very interesting, but really that's the boring part -- lots of trial and error, padding memory, etc.

• ashleyn 6y ago
  I suspect linked lists are not used because they are notorious for wrecking cache performance.
  • pfundstein 6y ago
    Never head of that, though I don't use C much. Are you referring to the CPU cache?
    • saagarjha 6y ago
      Yeah, linked lists are bad for the data cache since each element is in some totally random area of memory and thus less likely to be in a cache. Whereas for a linear array the data is next to each other and can be cached effectively and accesses can be easily predicted.
      • philsnow 6y ago
        You can also force-align (with padding if necessary) your structures to be along whatever boundaries make sense for your processor's cache lines. Ensuring an oft-loaded structure always fits inside a single cache line (instead of splaying across ~1.9 cache lines on average) is good not only for fitting lots of those structures into your L1 but for not blowing out cache bandwidth (read _and_ write, if you're modifying them).
        • a_t48 6y ago
          It's much more difficult to prefetch them, though - if you're traversing a large list it misses the cache every time, rather than just the first element. (someone please correct me if I'm wrong)
          • asdfasgasdgasdg 6y ago
            That's right. The reason why you see linked lists so much in old C stuff is (IMO) similar to the reason you see null terminated strings (and the associated bugs if you truncate incorrectly). And that's because of one of C's original sin: the failure to include size information in array objects. There is also the claim that linked lists are better in certain types of performance sensitive code because you can sometimes avoid allocating. I don't fully understand the logic there myself but I trust that there are cases where this is true.
            • pushrax 6y ago
              If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element). A linked list also avoids copying the entire array when you need to insert more elements than you have allocated space for.
              • cma 6y ago
                Depends on element size and some other stuff, but if it is a singly linked list, and truely random insertion location, iterating to that location is N/2 on average, where inserting and copying the rest of the array is also N/2. Small elements and the array could still be much faster since they are all prefetched during the copy, vs jumping all over memory during the list iteration and potentially stalling on each for ~200 instructions waiting on main memory.
                • saagarjha 6y ago
      • pushrax 6y ago
        Expanding on this: usually linked lists allocate each element with a separate malloc() on the heap, so they end up all over the place in memory. You could, in principle, allocate your linked list out of contiguous memory in such a way that sequentially reading the list doesn't cause so many page accesses. That would itself be a complicated data structure to maintain, so simply using a linear array is often the right tradeoff.
        • AlotOfReading 6y ago
          That's just a slab allocator. They're not what I'd call trivial, but still simple enough to be common in small projects and CS homework. I agree that an array is still generally simpler though.
          • pushrax 6y ago
            Once you are implementing your own allocator you need to worry about fragmentation under many operations, which would be the majority of the complexity.
      • yencabulator 6y ago
        Some 20 years ago, when I was a kernel developer with high performance requirements, my favorite data structure was a linked list of smallish arrays. Each array was small enough to be cheap to completely rewrite on insert/delete, if you needed to e.g. preserve insertion order; most of the time, it was enough to preserve order only across the linked list, treat each array like a hash table slot, or sort at consumption time.
        • skavi 6y ago
          I’ve considered making a vector sorta thing implemented as a linked list of arrays. Assuming you sized the arrays to fit well inside the CPU cache, are there really many tradeoffs?
          • yencabulator 6y ago
            Even if the array overflows the cache, it's not too bad for most access patterns. CPUs will easily prefetch data on a linear scan, so the "second half of the array" will most definitely be in cache by the time you get there. And a linear scan-once shouldn't even evict too much other stuff out of the cache. In practice, I would let benchmarks decide the array size. Modern CPUs are surprisingly good at prefetching even linked lists, and x86 works weird out-of-order magic and speculation while waiting for memory. My rules of two thumbs were 1) where performance really matters, don't trust your intuition, program and benchmark alternative implementations 2) don't trust microbenchmarks, e.g. total icache pressure changes whether inlining is good or not.
          • jacoblambda 6y ago
            It sounds like you are talking about an unrolled linked list[1]. I'd argue in most cases that while they are better than linked lists in just about every way (except data objects larger than the cache line), in most cases there is a better data structure to use. I'd find that the hashed array tree[2] would likely be a better/more versatile data structure solely due to the improved lookup time. [1]: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list [2]: https://en.wikipedia.org/wiki/Hashed_array_tree https://en.wikipedia.org/wiki/Hashed_array_tree
    • netheril96 6y ago
      The language doesn't matter. In almost all languages linked list has worse performance due to cache.
      • pfundstein 6y ago
        Forgive me but are linked lists common in other languages?
        • smabie 6y ago
          Super common? Main data structure in Scala, any kind of Lisp, Haskell, Erlang, etc. Linked lists are a functional programmer's goto data structure.
          • pfundstein 6y ago
            Well that would explain why I've only encountered them in C.
            • azernik 6y ago
              C is the only language where they're called "linked lists"; everything else just calls them "lists".
              • pjmlp 6y ago
                Nope, plenty of literature refers to them as linked lists. Here is an article about them in Modula-2, to use a language of similar age as C. https://www.modula2.org/tutor/chapter11.php https://www.modula2.org/tutor/chapter11.php
                • azernik 6y ago
                  I was being loose with the words "everything" and "only". GP comment was curious about why they've only heard about "linked lists" in a language, C, which like Modula-2 does not use them as the basic standard library collections type. When you have to implement linked lists yourself if you want to use them, you're always going to refer to them by implementation detail. In the vast majority of cases where they're used, though, it's as the fundamental standard library collection, and in that case they're usually just called Lists without telling the caller about their implementation. (This idiom is true to the point that the Python implementers feel the need to point out that CPython uses arrays to implement the list type, as they feel that this would be unexpected to users of other languages that call their basic collections type a "list".)
  • dilyevsky 6y ago
    Same is true for other trees such as std::map
• saagarjha 6y ago
  Apple uses tons of linked lists, I'm not sure why you got the impression that they don't?
  • dvt 6y ago
    I was referring specifically to the list of `IO80211AWDLPeer`s the author was reverse-engineering. His assumption was that the `IO80211AWDLPeer`s were in a linked-list type of data structure (which is a pretty sensible guess). In fact, it ended up being more akin to a priority queue: > The data structure holding the peers is in fact much more complex than a linked list, it's more like a priority queue with some interesting behaviours when the queue is modified and a distinct lack of safe unlinking and the like. I amended my post for clarification, I'm sure Apple uses linked lists all the time :)
• fulafel 6y ago
  > How did this even pass the _smell_ test? Because attackers only have to find one place that was unlucky in implementation, and hence defenders are burdened with eliminting every last one of them. This is why implementing your network protocols in unsafe languages is bad. Testing can just find some bugs, not ensure absence of bugs.
  • geocar 6y ago
    If it's not one thing, it's another. https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=rust https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=rust Now I know it's deeply comforting to think if you just had "safety" you could write all the code you want with abandon and the computer would tell you if you did it wrong, but this is a sophomoric attitude that you will either abandon when you have the right experiences, or you will go into management where the abject truth in this statement will be used to keep programmer salaries in the gutter, and piss-poor managers in a job. Meanwhile, these "safe" languages will give you nothing but shadows you'll mistake for your own limitations. My suggestion is just learn how to write secure code in C. It's an unknown-unknown for you at the moment, so you're going to have to learn how to tackle that sort of thing, but the good news is that (with the right strategy) many unknown-unknowns can be attacked using the same tricks. That means if you do learn how to write secure code in C, then the skills you develop will be transferable to other languages and other domains, and if you still like management, those skills will even be useful there.
    • krisoft 6y ago
      > My suggestion is just learn how to write secure code in C. That is a good suggestion to an individual developer. What is your suggestion to a lead developer of a big organisation? Let’s say to the CTO of Apple. You can see at that level of abstraction the “make sure every one of your developers know how to write secure code in C and they never slip up” manifestly doesnt work. You can fault individuals for bugs up to a certain point, but if we want to make secure systems we have to change how we are making them. To make the whole process resistant to oopsies.
      • 6y ago
• tikiman163 6y ago
  Finding the bug that allowed this exploit took this researcher weeks. QA can't find all defects without somehow testing every conceivable scenario without knowing every conceivable scenario, and code review can only catch defects if at least one reviewer is able to somehow know that specific methods make an exploit possible. Given that the exact code of underlying methods used may not be known to code reviewers, or that a reviewer might simply not know the full potential use cases for new code at the time of review, it is entirely understandable that defects and resulting exploits happen. This is why researchers like the OP exist. They find exploits and report them to the manufacturer (hopefully) before they can be used. The fact that this is an effective way of protecting us is also why major software companies offer bug/exploit bounties to researchers. To demand that all possible exploits of this nature never find their way into production builds is to demand perfection from humans. There is too much to know and think about, and definitely too many unknowns about the future, to make such a fantasy possible while still meeting release deadlines. We software developers often have a hard enough time just meeting feature and documentation deadlines, and adding more people just makes organizing your efforts more complex and difficult which then requires even more people until you reach the point that the scope of organizing your development teams is financially impossible.
  • saagarjha 6y ago
    Well, the majority of the time went into being able to turn the bug into an exploit.