Просмотр сообщений

В этом разделе можно просмотреть все сообщения, сделанные этим пользователем.


Сообщения - kkkk

Страницы: 1 2 3 [4] 5 6 ... 9
46
Общий раздел / Re: Oberon-07/13: заметки
« : Октябрь 24, 2016, 02:00:24 pm »
Был у меня в своё время парсер языка Си.  Однажды я тоже запустил профилировщик и обнаружил, что уйму времени занимает проверка идентификаторов на принадлежность к ключевым словам. Написана она была, разумеется, без цикла Дейкстры - обычный линейный поиск на while(). Тогда я по памяти написал за пол-часа поиск через ассоциативный массив, что сняло нагрузку, но практического смысла в этом не было.

47
Общий раздел / Re: Simit
« : Октябрь 08, 2016, 01:55:21 pm »
Если не компилируются, то дело не статическом анализаторе. Во-первых, gcc использует свой диалект, и в общем случае собранное в gcc гарантированно собирается только gcc. Во-вторых, VS использует диалект Си, который является расширением подмножества стандартного Си.

48
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 30, 2016, 01:39:49 pm »
Верно, поскольку компьтер - это функциональный эквивалент машины Тьюринга с ограничением на память, которой, впрочем, достаточно, чтобы этим пренбречь. Раз проблема возможна в полном по Тьюрингу языке, то проблема есть и в аналоге Тьюринг-машины, то есть компьютере. Эти размышления имеют теоретический смысл, а о большем я и не говорил.

Обратите внимание, изначально я тоже напирал на практическую сторону, объяснив, что в Си такой ошибки не возникнет, но Алексей настаивал, что возникнет. Он дополнил Си до семантики С++, достаточной для этой задачи, предложив использовать вектор, написанный на Си. Обычно сишники так не поступают, они стараются использовать более простые средства, но принципиальная-то возможность есть, благо и копать недалеко. Позже мне пришло в голову, что  с такой точки зрения все языки уязвимы, так как любой полный по Тьюрингу язык можно дополнить до семантики С++. В общем случае, конечно, копать придётся глубоко и никто в здравом уме не станет этого делать, но мы, прикинувшись математиками, делаем вид, что нам всё равно.

49
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 30, 2016, 10:59:30 am »
Твой тезис имел бы смысл, сформулируй ты его иначе: эта ошибка возможна в любом языке, для которого можно написать транслятор из с++, полностью сохранающий семантику исходной программы.

Ну так для хаскелла, выходит, такого транслятора нельзя создать, потому что семантика не сохраняется.
Более того, подозреваю, что разные компиляторы с++ могут по разному компилировать эту программу, по разному понимая семантику этой программы. Где-то будет получаться эта ошибка, где-то не будет...
Вы уверждаете, что транслятор С++, написанный на Хаскелле вместе с программой на С++, всунутой в строку в исходнике на Хаскелле, не является программой, написанной на Хаскелле? Если нет, то что не так? Обратите внимание, что речь не о практической достижимости, а о принципиальной возможности. Конечно, такой принципиальной возможности можно достичь гораздо более простым путём, чем создание транслятора C++, но версия с транслятором веселей и наглядней.

50
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 29, 2016, 08:04:07 pm »
Покажите мне язык где подобная ошибка не может возникнуть в принципе!
Я только сейчас обратил внимание на категоричность запроса - не может возникнуть в принципе. Возможно, Алексей захотел пошутить, потому что, в принципе, в любом полном по Тьюрингу языке, такая ошибка может возникнуть.

Рассмотрим доказательство. Как мы уже выяснили,  в С++ такая ошибка возможна, а значит, возможна везде, где можно создать  виртуальную машину и компилятор С++ для неё, который соберёт приведённую программу с ошибкой. Это возможно в любом полном по Тьюрингу языке. Доказано.

Так что все эти ваши обероны, хаскели и даже русские коболы уязвимы.

51
Общий раздел / Re: Oberon 2016
« : Сентябрь 29, 2016, 11:27:44 am »
Хе-хе. Вирта задолбало и он вернул тайпдефы? :)
Судя по описанию - это всего лишь синтаксическое послабление, но семантика осталась прежней.

52
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 29, 2016, 10:58:56 am »
Вообще-то аналогичная проблема была бы возможна и в обероне, если бы кто-то удосужился в нём реализовать класс вектор. Впрочем, думаю, можно и обероновским массивом такое же провернуть.
Эта проблема невозможна в Обероне ни с вектором ни с массивом. Может я ошибаюсь, но тогда покажите как.

53
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 10:54:08 pm »
О таком фокусе я знаю, но в общем случае резерва не требуется, в то время как в Си - он обязателен.
Какие-то странные представления о Си. Конечно же и в Си это не обязательно.
У меня действительно странные представления о Си - основаны на логике и опыте ежедневного использования, к счастью и к сожалению. В Си в невыделенной памяти  ничего работать не будет и это очевидно. Даже если программист перепил чаю и забыл выделить память, после первого же неудачного запуска он это исправит. В С++ с вектором в большинстве случаев можно не волноваться, Tefal думает за вас. Но иногда это выливается в непонимание, как работает программа и приходится тратить немало времени, чтобы выяснить причину проблемы. Речь об этом.
 

Цитировать
Выделить сразу памяти столько сколько будет необходимо в общем случае либо невозможно, либо слишком ресурсоёмко для подобных классов задачек как минимум.
В общем случае - нет, а в частном зачастую есть асимптотические формулы, позволяющие найти достаточно хорошее приближение сверху, и именно такое выделение будет самым эффективным по скорости. И памяти нужно в 1.5-2 раза меньше, чем с саморасширяющимся вектором(при удачных для вектора раскладах - одинаковое). К тому же, не надо во время вычисления обрабатывать отказ от выделения очередной порции памяти - хватит или нет ясно в самом начале.

Цитировать
На тему явного и очевидного, то в Си в реальном коде, это смотрелось бы примерно так, на самом деле.
g_array_index(ts, bor, v).mp[x] = go();
...
int go() {
        bor b;
        init(&b);
        g_array_append_val(ts, b);
        return ts->len-1;
}
И ровно с той же семантикой.
Даже при повторении семантики один в один, проблема в Си видна гораздо лучше, потому что в нём нет возможности для самописных структур и функций мимикрировать под массивы, а потому вводить в заблуждение.

Цитировать
Никто по сто раз писать один и тот же велосипед для банального динамического массива/вектора не будет ни в одном из языков. Все либо пишут свои либы, либо используют уже написанные.
А я реализовал нечто подобное, только коллеги это отвергли.

Цитировать
Ну, то есть по сути ты говоришь, что это не С++ плохой как язык и им не надо пользоваться, а это использование готовых либ плохо и ими не следует пользоваться в любом языке, следует максимально на каждый чих писать велосипед.
Нет, я этого не говорю, да и что такое плохой язык, я тоже плохо понимаю.

Цитировать
Причем сколько мест использования подобного кода, столько велосипедов в проекте и должно быть. Так сказать, по велосипеду отдельному на каждое место использования :-)
А это зависит от задачи, решаемой библиотекой или велосипедом. Для банального кода лучше велосипед по месту без запрета на переиспользование неподалёку. Нередко оказывается экономичней помнить базовые принципы и уметь их быстро воплощать, чем помнить и разбираться в нюансах редкоиспользуемой библиотеки с постоянным сверением с документацией.  Для нетривиального кода, например, компрессора данных - однозначно нужно использовать готовое решение, если оно достаточно хорошо для твоей задачи.
Есть ещё вопрос лицензий. Я, как пролетарий, сталкиваюсь с тем, что часто не могу использовать свой старый код. Чтобы переиспользовать нужно получить непростое разрешение на выкладывание в Open Source. Дело благородное, но также сопряжено с дополнительными затратами на оформление кода, соответствующее уровню компании, как в ней это видят. И вот для такой банальщины, как вектор,  проще всего оказывается наколбасить по месту либо использовать ещё более простое решение, и часто это работает.

54
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 12:08:50 pm »
Дык и тут ровно то же самое :-) Смотри, фокус покажу:
переписываем main вот так:
int main()
{
    tr.reserve(100500);
    go();
    s = "01";
    add(0, 0, 1);
}

И ничего уже никуда не падает, память не портится :-)
О таком фокусе я знаю, но в общем случае резерва не требуется, в то время как в Си - он обязателен.

Не массив, а указатель на массив. И смотрелось бы это так:
size_t len = 1;
bor* tr = malloc(len*sizeof(bor));

tr[v].mp[x] = go();
...
int go()
{
    bor* old = tr;
    len++;
    tr = malloc(len * sizeof(bor));
    memcpy(tr, old, (len-1)*sizeof(bor));
    free(old);
    bor b;
    init(&b);
    tr[len-1] = b;
    return len-1;
}
В том-то и дело, что для Си это
  • Трудоёмко, поэтому чаще будет задействовано более простое решение - выделения столько памяти, сколько должно хватить для всех допустимых случаев, возможно, по формуле
  • Даже если реализовано автоувеличение размера, оно явное и очевидное, что делает проблему более понятной и менее вероятной

55
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 11:38:55 am »
Не понимаю, как это могло привести к падению программы?
1. сначала была выполнена  tr[v].mp[x] , которая ссылалась на массив, использованный в vector в текущем состоянии.
2. затем go() добавила новый элемент в tr, что потребовало выделения нового массива и освобожения старого
3.  наконец было выполнено присваивание tr[v].mp[x] = go() , которое произвело запись в освобождённую память

56
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 11:34:17 am »
Очевидно, что очевидная проблема не столь очевидна, коль было столь длинное и долгое обсуждение с массой неверных гипотез. :-)
Очевидной она стала после использования средств контроля целостности памяти. Стало понятно, что обращение идёт не к тому, что изначально предполагалось, и оставалось только выяснить почему.

Что такое плохое понимание универсальных решений, я не очень понял.
Объект-хранилище как универсальное решение мимикрирует под то, чем он не является - под массив, чем вводит в заблуждение. Будь там банальный массив, проблемы бы тоже не было, если бы, конечно, было бы выделено достаточно памяти для него.

Теперь осталось ответить на второй вопрос - на вашем любимом ЯП возможна ли подобная ошибка?
В Си такой ошибки бы не было, потому что для него использовали бы массив, а не vector.

57
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 11:14:57 am »
tr[v].mp[x] = go();
Очевидная проблема в этом месте, так как go() изменяет tr.
Если изменить на
int tmp = go();
tr[v].mp[x] = tmp;
То всё нормально. Да, проблема в плохом понимании работы универсальных решений. И в наличии состояния, конечно  :D

58
Общий раздел / Re: Найдите ошибку, если она есть.
« : Сентябрь 28, 2016, 09:54:53 am »
Решил глянуть на этот код.
Собрал "g++-5 -std=gnu++11 -g", запустил. Программа нормально завершилась выдав:
go 1 0
in 0 1 0 2
go in
1 0
go 2 1
2 0
go out
in 0 2 1 2
go in
2 0
go 3 2
3 0
go out
in 0 3 2 2
Я что-то упустил из виду?
Собрал по-другому - "g++ -std=c++11 -g -fsanitize=address -fsanitize=undefined" . Запустил - теперь она грохнулась на использовании освобождённой памяти
go 1 0
in 0 1 0 2
go in
1 0
go 2 1
=================================================================
==5542==ERROR: AddressSanitizer: heap-use-after-free on address 0x60200000eff0 at pc 0x000000402abf bp 0x7fff0f67c930 sp 0x7fff0f67c920
WRITE of size 4 at 0x60200000eff0 thread T0
    #0 0x402abe in add(int, int, int) /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36
    #1 0x40301a in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:47
    #2 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #3 0x4018c8 in _start (/home/konstantin/projects/github/bubble_test/cpp-strange-error/a.out+0x4018c8)

0x60200000eff0 is located 0 bytes inside of 12-byte region [0x60200000eff0,0x60200000effc)
freed by thread T0 here:
    #0 0x7f3bef767b2a in operator delete(void*) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99b2a)
    #1 0x404a5b in __gnu_cxx::new_allocator<bor>::deallocate(bor*, unsigned long) /usr/include/c++/5/ext/new_allocator.h:110
    #2 0x4044bb in std::allocator_traits<std::allocator<bor> >::deallocate(std::allocator<bor>&, bor*, unsigned long) /usr/include/c++/5/bits/alloc_traits.h:517
    #3 0x403ce2 in std::_Vector_base<bor, std::allocator<bor> >::_M_deallocate(bor*, unsigned long) /usr/include/c++/5/bits/stl_vector.h:178
    #4 0x4041f2 in void std::vector<bor, std::allocator<bor> >::_M_emplace_back_aux<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:438
    #5 0x403b35 in void std::vector<bor, std::allocator<bor> >::emplace_back<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:101
    #6 0x403498 in std::vector<bor, std::allocator<bor> >::push_back(bor&&) /usr/include/c++/5/bits/stl_vector.h:932
    #7 0x401a62 in go() /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:16
    #8 0x402a5e in add(int, int, int) /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36
    #9 0x40301a in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:47
    #10 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

previously allocated by thread T0 here:
    #0 0x7f3bef767532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x404d73 in __gnu_cxx::new_allocator<bor>::allocate(unsigned long, void const*) /usr/include/c++/5/ext/new_allocator.h:104
    #2 0x404c03 in std::allocator_traits<std::allocator<bor> >::allocate(std::allocator<bor>&, unsigned long) /usr/include/c++/5/bits/alloc_traits.h:491
    #3 0x404920 in std::_Vector_base<bor, std::allocator<bor> >::_M_allocate(unsigned long) /usr/include/c++/5/bits/stl_vector.h:170
    #4 0x403e0a in void std::vector<bor, std::allocator<bor> >::_M_emplace_back_aux<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:412
    #5 0x403b35 in void std::vector<bor, std::allocator<bor> >::emplace_back<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:101
    #6 0x403498 in std::vector<bor, std::allocator<bor> >::push_back(bor&&) /usr/include/c++/5/bits/stl_vector.h:932
    #7 0x401a62 in go() /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:16
    #8 0x402ff7 in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:45
    #9 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: heap-use-after-free /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36 add(int, int, int)
Shadow bytes around the buggy address:
  0x0c047fff9da0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9db0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9de0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c047fff9df0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa[fd]fd
  0x0c047fff9e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==5542==ABORTING
Похоже, такое действительно не во всех языках возможно. Налицо избыточная сложность "универсального хорошо отлаженного" решения,  и поэтому трудно понять, что оно там внутри делает. По-моему, тут не с ошибкой надо разбираться, а навелосипедить более простое, хотя и более объёмное решение.


59
Где версия для Оберона?

60
Тогда всё сходится. Без вывода остальные программы работают быстрей, не только в ББ.

clang (o7 -> c) - 0.49 сек
clang++ (cpp)  - 0.53 сек

Страницы: 1 2 3 [4] 5 6 ... 9