aqeq's blog

By aqeq, history, 4 hours ago, In English

In a nutshell

#define _GLIBCXX_SANITIZE_VECTOR 1

Prerequisites

Many of you know about _GLIBCXX_DEBUG / _GLIBCXX_DEBUG_PEDANTIC defines that force libstdc++ on GCC compilers to check out-of-bounds access to the array and react correspondingly. Linux (and some Mac OS users that use clang as a compiler) may also know about libasan library (that you can activate via providing -fsanitize=address parameter to the build option. It checks not only for STL containers, but also every possible out-of-bounds memory access. While it may seem like it's going to work on std::vector out-of-bounds access, that's not always the case. See the example below.

#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4};
    int variable = arr[4];
}

This will trigger the libasan check, as the allocated capacity of the vector equals to the size of the vector. More on how std::vector works you may read here.

In a nutshell: std::vector allocated some capacity that is >= than size, and after each push_back if capacity becomes lower than size it reallocates everything and doubles the capacity.

So what's the problem? Why doesn't it work in all of the cases?

You see, when size < capacity, the allocated memory length is actually the size of capacity.

Imagine a situation: size equals to 9, capacity equals to 16. You access arr[9] and that won't go out-of-bounds from the point of an OS. Libasan won't trigger. You can test this code to prove that:

#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4};
    arr.reserve(10000);
    int variable = arr[4];
}

What you have come for

If you pass #define _GLIBCXX_SANITIZE_VECTOR 1 before including any libraries, libasan will trigger on container overflow in all of the cases. You can try the above example and see that it will work. So, the edited code will be:

#define _GLIBCXX_SANITIZE_VECTOR 1
#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4};
    arr.reserve(10000);
    int variable = arr[4];
}

Motivation

I haven't seen any mentions of this on codeforces yet, so may be that would be helpful to someone.

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aqeq (previous revision, new revision, compare).

»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

OH MY FUCKING GOD THATS INCREDIBLE

»
4 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

How he solved the problem for a long time and finally found its solution

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

REALL!!!!!!!!!! LOVE IT!!

»
3 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

wow O.o

»
3 hours ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

>.<