{"id":1350,"date":"2018-02-07T13:07:26","date_gmt":"2018-02-07T13:07:26","guid":{"rendered":"http:\/\/dlang.org\/blog\/?p=1350"},"modified":"2021-10-08T11:06:11","modified_gmt":"2021-10-08T11:06:11","slug":"vanquish-forever-these-bugs-that-blasted-your-kingdom","status":"publish","type":"post","link":"https:\/\/dlang.org\/blog\/2018\/02\/07\/vanquish-forever-these-bugs-that-blasted-your-kingdom\/","title":{"rendered":"Vanquish Forever These Bugs That Blasted Your Kingdom"},"content":{"rendered":"

Walter Bright<\/a> is the BDFL of the D Programming Language and founder of Digital Mars<\/a>. He has decades of experience implementing compilers and interpreters for multiple languages, including Zortech C++, the first native C++ compiler. He also created Empire, the Wargame of the Century<\/a>. This post is the second in a series<\/a> about\u00a0D\u2019s BetterC mode<\/a>.<\/em><\/p>\n

\n

\"\"<\/p>\n

Do you ever get tired of bugs that are easy to make, hard to check for, often don\u2019t show up in testing, and blast your kingdom<\/a> once they are widely deployed? They cost you time and money again and again. If you were only a better programmer, these things wouldn\u2019t happen, right?<\/p>\n

Maybe it\u2019s not you at all. I\u2019ll show how these bugs are not your fault – they\u2019re the tools\u2019 fault, and by improving the tools you\u2019ll never have your kingdom blasted by them again.<\/p>\n

And you won\u2019t have to compromise, either.<\/p>\n

Array Overflow<\/h3>\n

Consider this conventional program to calculate the sum of an array:<\/p>\n

#include <stdio.h>\r\n\r\n#define MAX 10\r\n\r\nint sumArray(int* p) {\r\n    int sum = 0;\r\n    int i;\r\n    for (i = 0; i <= MAX; ++i)\r\n        sum += p[i];\r\n    return sum;\r\n}\r\n\r\nint main() {\r\n    static int values[MAX] = { 7,10,58,62,93,100,8,17,77,17 };\r\n    printf(\"sum = %d\\n\", sumArray(values));\r\n    return 0;\r\n}<\/pre>\n
The program should print:<\/p>\n
sum = 449<\/pre>\n
And indeed it does, on my Ubuntu Linux system, with both gcc<\/code> and clang<\/code> and -Wall<\/code>. I\u2019m sure you already know what the bug is:<\/p>\n
for (i = 0; i <= MAX; ++i)\r\n              ^^<\/pre>\n
This is the classic \u201cfencepost problem<\/a>\u201d. It goes through the loop 11 times instead of 10. It should properly be:<\/p>\n
for (i = 0; i < MAX; ++i)<\/pre>\n
Note that even with the bug, the program still produced the correct result! On my system, anyway. So I wouldn\u2019t have detected it. On the customer\u2019s system, well, then it mysteriously fails, and I have a remote heisenbug<\/a>. I\u2019m already tensing up anticipating the time and money this is going to cost me.<\/p>\n
It\u2019s such a rotten bug that over the years I have reprogrammed my brain to:<\/p>\n
    \n
  1. Never, ever use \u201cinclusive\u201d upper bounds.<\/li>\n
  2. Never, ever use <=<\/code> in a for loop condition.<\/li>\n<\/ol>\n
    By making myself a better programmer, I have solved the problem! Or have I? Not really. Let\u2019s look again at the code from the perspective of the poor schlub who has to review it. He wants to ensure that sumArray()<\/code> is correct. He must:<\/p>\n
      \n
    1. Look at all callers of sumArray()<\/code> to see what kind of pointer is being passed.<\/li>\n
    2. Verify that the pointer actually is pointing to an array.<\/li>\n
    3. Verify that the size of the array is indeed MAX<\/code>.<\/li>\n<\/ol>\n
      While this is trivial for the trivial program as presented here, it doesn\u2019t really scale as the program complexity goes up. The more callers there are of sumArray<\/code>, and the more indirect the data structures being passed to sumArray<\/code>, the harder it is to do what amounts to data flow analysis in your head to ensure it is correct.<\/p>\n
      Even if you get it right, are you sure? What about when someone else checks in a change, is it still right? Do you want to do that analysis again? I\u2019m sure you have better things to do. This is a tooling problem.<\/p>\n
      The fundamental issue with this particular problem is that a C array decays to a pointer when it’s an argument to a function, even if the function parameter is declared to be an array. There\u2019s just no escaping it. There\u2019s no detecting it, either. (At least gcc and clang don\u2019t detect it, maybe someone has developed an analyzer that does).<\/p>\n
      And so the tool to fix it is D as a BetterC<\/a> compiler. D has the notion of a dynamic array<\/em>, which is simply a fat pointer, that is laid out like:<\/p>\n
      struct DynamicArray {\r\n    T* ptr;\r\n    size_t length;\r\n}<\/pre>\n
      It\u2019s declared like:<\/p>\n
      int[] a;<\/pre>\n
      and with that the example becomes:<\/p>\n
      import core.stdc.stdio;\r\n\r\nextern (C):   \/\/ use C ABI for declarations\r\n\r\nenum MAX = 10;\r\n\r\nint sumArray(int[] a) {\r\n    int sum = 0;\r\n    for (int i = 0; i <= MAX; ++i)\r\n        sum += a[i];\r\n    return sum;\r\n}\r\n\r\nint main() {\r\n    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];\r\n    printf(\"sum = %d\\n\", sumArray(values));\r\n    return 0;\r\n}<\/pre>\n
      Compiling:<\/p>\n
      dmd -betterC sum.d<\/pre>\n
      Running:<\/p>\n
      .\/sum\r\nAssertion failure: 'array overflow' on line 11 in file 'sum.d'<\/pre>\n
      That\u2019s more like it. Replacing the <=<\/code> with <<\/code> we get:<\/p>\n
      .\/sum\r\nsum = 449<\/pre>\n
      What\u2019s happening is the dynamic array a<\/code> is carrying its dimension along with it and the compiler inserts an array bounds overflow check.<\/p>\n
      But wait, there\u2019s more.<\/p>\n
      There\u2019s that pesky MAX<\/code> thing. Since the a<\/code> is carrying its dimension, that can be used instead:<\/p>\n
      for (int i = 0; i < a.length; ++i)<\/pre>\n
      This is such a common idiom, D has special syntax for it:<\/p>\n
      foreach (value; a)\r\n    sum += value;<\/pre>\n
      The whole function sumArray()<\/code> now looks like:<\/p>\n
      int sumArray(int[] a) {\r\n    int sum = 0;\r\n    foreach (value; a)\r\n        sum += value;\r\n    return sum;\r\n}<\/pre>\n
      and now sumArray()<\/code> can be reviewed in isolation from the rest of the program. You can get more done in less time with more reliability, and so can justify getting a pay raise. Or at least you won\u2019t have to come in on weekends on an emergency call to fix the bug.<\/p>\n
      \u201cObjection!\u201d you say. \u201cPassing a<\/code> to sumArray()<\/code> requires two pushes to the stack, and passing p<\/code> is only one. You said no compromise, but I\u2019m losing speed here.\u201d<\/p>\n
      Indeed you are, in cases where MAX<\/code> is a manifest constant, and not itself passed to the function, as in:<\/p>\n
      int sumArray(int *p, size_t length);<\/pre>\n
      But let\u2019s get back to \u201cno compromise.\u201d D allows parameters to be passed by reference,
      \nand that includes arrays of fixed length. So:<\/p>\n
      int sumArray(ref int[MAX] a) {\r\n    int sum = 0;\r\n    foreach (value; a)\r\n        sum += value;\r\n    return sum;\r\n}<\/pre>\n
      What happens here is that a<\/code>, being a ref<\/code> parameter, is at runtime a mere pointer. It is typed, though, to be a pointer to an array of MAX<\/code> elements, and so the accesses can be array bounds checked. You don\u2019t need to go checking the callers, as the compiler\u2019s type system will verify that, indeed, correctly sized arrays are being passed.<\/p>\n
      \u201cObjection!\u201d you say. \u201cD supports pointers. Can\u2019t I just write it the original way? What\u2019s to stop that from happening? I thought you said this was a mechanical guarantee!\u201d<\/p>\n
      Yes, you can write the code as:<\/p>\n
      import core.stdc.stdio;\r\n\r\nextern (C):   \/\/ use C ABI for declarations\r\n\r\nenum MAX = 10;\r\n\r\nint sumArray(int* p) {\r\n    int sum = 0;\r\n    for (int i = 0; i <= MAX; ++i)\r\n        sum += p[i];\r\n    return sum;\r\n}\r\n\r\nint main() {\r\n    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];\r\n    printf(\"sum = %d\\n\", sumArray(&values[0]));\r\n    return 0;\r\n}<\/pre>\n
      It will compile without complaint, and the awful bug will still be there. Though this time I get:<\/p>\n
      sum = 39479<\/pre>\n
      which looks suspicious, but it could have just as easily printed 449 and I\u2019d be none the wiser.<\/p>\n
      How can this be guaranteed not to happen? By adding the attribute @safe<\/code> to the code:<\/p>\n
      import core.stdc.stdio;\r\n\r\nextern (C):   \/\/ use C ABI for declarations\r\n\r\nenum MAX = 10;\r\n\r\n@safe int sumArray(int* p) {\r\n    int sum = 0;\r\n    for (int i = 0; i <= MAX; ++i)\r\n        sum += p[i];\r\n    return sum;\r\n}\r\n\r\nint main() {\r\n    __gshared int[MAX] values = [ 7,10,58,62,93,100,8,17,77,17 ];\r\n    printf(\"sum = %d\\n\", sumArray(&values[0]));\r\n    return 0;\r\n}<\/pre>\n
      Compiling it gives:<\/p>\n
      sum.d(10): Error: safe function 'sum.sumArray' cannot index pointer 'p'<\/pre>\n
      Granted, a code review will need to include a grep to ensure @safe<\/code> is being used, but that\u2019s about it.<\/p>\n
      In summary, this bug is vanquished by preventing an array from decaying to a pointer when passed as an argument, and is vanquished forever by disallowing indirections after arithmetic is performed on a pointer. I\u2019m sure a rare few of you have never been blasted by buffer overflow errors. Stay tuned for the next installment in this series. Maybe your moat got breached by the next bug! (Or maybe your tool doesn\u2019t even have a moat.)<\/p>\n","protected":false},"excerpt":{"rendered":"
      Do you ever get tired of bugs that are easy to make, hard to check for, often don\u2019t show up in testing, and blast your kingdom once they are widely deployed? They cost you time and money again and again. If you were only a better programmer, these things wouldn\u2019t happen, right?<\/p>\n","protected":false},"author":15,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[31,26,8],"tags":[],"_links":{"self":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1350"}],"collection":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/comments?post=1350"}],"version-history":[{"count":13,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1350\/revisions"}],"predecessor-version":[{"id":1595,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/1350\/revisions\/1595"}],"wp:attachment":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/media?parent=1350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/categories?post=1350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/tags?post=1350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}