Przez techniczne serwisy przeleciała ostatnio informacja o poważnym błędzie w kodzie Gita (w Polsce pisał o nim choćby Niebezpiecznik). News jak news, różnorakie usterki są odkrywane na pęczki ale jako uczestnik świętej wojny Gita z Mercurialem rzuciłem okiem. Błąd okazał się całkiem ciekawy i … potrącił interesującą mnie sprawę.
Błąd
Problematyczny kod jest cytowany tutaj. Jest nim funkcja składająca pełną nazwę pliku z zapisanych w formie listy fragmentów:
char *path_name(const struct name_path *path, const char *name)
{
const struct name_path *p;
char *n, *m;
int nlen = strlen(name);
int len = nlen + 1;
for (p = path; p; p = p->up) {
if (p->elem_len)
len += p->elem_len + 1;
}
n = xmalloc(len);
m = n + len - (nlen + 1);
memcpy(m, name, nlen + 1);
for (p = path; p; p = p->up) {
if (p->elem_len) {
m -= p->elem_len + 1;
memcpy(m, p->elem, p->elem_len);
m[p->elem_len] = '/';
}
}
return n;
}
Czyli: iterujemy po liście, by wyliczyć łączną długość wszystkich elementów (z naddatkiem na separatory), alokujemy bufor tej długości a następnie kopiujemy do niego kolejne fragmenty. Wygląda niewinnie.
W czym błąd? Ano, jeżeli dane są odpowiednio złośliwe, łączna wyliczona długość może przepełnić zakres int-a i dać wynik niewielki albo wręcz ujemny. Na systemie 32-bitowym, wyliczając rozmiar bufora potrzebny do zapisania nazwy złożonej z czterech fragmentów długości (powiedzmy) 230 oraz jednego długości 10, uzyskamy len = 15. Program zaalokuje zatem 15 bajtów a następnie będzie pod uzyskany adres kopiował duże oryginalne bufory (fakt, że mamy tu odliczanie do tyłu i cofanie wskaźnika, jeszcze dodaje atrakcyjności).
Przy bardziej praktycznym planowaniu ataku, należałoby sprowokować
użycie tej funkcji na odpowiednich danych - zapewne wykreować
repozytorium zawierające (być może tylko w metadanych) odpowiedniej
długości ścieżki a potem podsunąć je ofierze do pull. Odpowiedni
napis to (zależnie od rodzaju szukanego przepełnienia) 2GB lub 4GB co
jest w dzisiejszych czasach całkiem praktyczne, zarówno z punktu
widzenia transferu plików, jak tworzenia reprezentacji w
pamięci. Zupełnie niewykluczone też, że w jakimś kontekście owe
ścieżki są zapisywane w formie skompresowanej.
Między C a C++
Piszę o tym, bo od zawsze jedną z moich małych alergii jest
niechęć do używania gołego C a zwłaszcza - o ile nie ma ku temu
naprawdę poważnej potrzeby - ręcznego manipulowania pamięcią
via memcpy, strcpy i całej gospodarki buforami. Która
potrafi doskonale unieczytelnić najprostszy kod i raz za razem
okazuje się podatna na taką czy inną lukę.
Cały powyższy algorytm możnaby (programując w C++) zapisać jakoś tak:
string path;
for (auto element : path_items) { // Albo dowolna inna iteracja
path += '/';
path += element;
}
return path;
Gdy rzuciłem tego typu uwagę, jeden z kolegów natychmiast odpowiedział ale to by dla dużych danych działało znacznie wolniej.
Cóż, czy wypieszczenie do maksimum wydajności tej funkcji ma jakiekolwiek znaczenie, śmiem wątpić ale … rzecz w sumie ciekawa. O ile właściwie więcej kosztuje to sumowanie stringów?
Zrobiłem prosty benchmark. Przy tym, skoro miałem rzucić okiem też na większe dane, poza powyższym zapisem, uwzględniłem też drugi:
string::size_type len = 0;
for(…) {
len += element.size() + 1;
}
string path;
path.reserve(len);
for (…) {
path += '/';
path += element;
}
Zwróćmy uwagę, że jeśli tutaj owo len się przewinie, nic złego się
nie stanie - po prostu kod zadziała jak gdyby wstępnego reserve
nie było, we właściwym momencie obiekt string zauważy brak miejsca
i po prostu doalokuje większy bufor.
Przykładowe wyniki benchmarka wypadły następująco (pierwsza kolumna to łączny czas na dużą ilość powtórzeń, druga to wynikający z dzielenia średni czas na jedną operację - w mikrosekundach):
Suma 5 napisow o rozmiarach 10-20 (wynik 65 bajtow). 2000000 iteracji
string: 1.25231 s/total 0.62615 us/op
string/reserve: 0.53982 s/total 0.26991 us/op
memcpy: 0.28404 s/total 0.14202 us/op
strcpy: 0.39457 s/total 0.19728 us/op
Suma 5 napisow o rozmiarach 17-16000 (wynik 100 bajtow). 2000000 iteracji
string: 1.33343 s/total 0.66672 us/op
string/reserve: 0.63119 s/total 0.31560 us/op
memcpy: 0.30030 s/total 0.15015 us/op
strcpy: 0.70579 s/total 0.35289 us/op
Suma 25 napisow o rozmiarach 5-40 (wynik 450 bajtow). 200000 iteracji
string: 0.51341 s/total 2.56705 us/op
string/reserve: 0.19894 s/total 0.99472 us/op
memcpy: 0.09938 s/total 0.49689 us/op
strcpy: 0.23004 s/total 1.15022 us/op
Suma 25 napisow o rozmiarach 9999-29999 (wynik 250300 bajtow). 10000 iteracji
string: 4.51477 s/total 451.47728 us/op
string/reserve: 0.56949 s/total 56.94879 us/op
memcpy: 0.48008 s/total 48.00797 us/op
strcpy: 0.93943 s/total 93.94335 us/op
Suma 10000 napisow o rozmiarach 5-40 (wynik 234888 bajtow). 5000 iteracji
string: 1.84888 s/total 369.77603 us/op
string/reserve: 1.78822 s/total 357.64416 us/op
memcpy: 0.95070 s/total 190.14011 us/op
strcpy: 2.36503 s/total 473.00524 us/op
Suma 10000 napisow o rozmiarach 2005-3440 (wynik 27199016 bajtow). 20 iteracji
string: 0.87778 s/total 43889.03820 us/op
string/reserve: 0.25458 s/total 12728.81025 us/op
memcpy: 0.25381 s/total 12690.47225 us/op
strcpy: 0.32733 s/total 16366.60230 us/op
Wyniki trzeba traktować z pewnym przymrużeniem oka (benchmark nie
jest zbyt finezyjny i wpływają nań choćby zachowania alokatorów)
ale coś pokazują. Proste sumowanie stringów jest kilkakrotnie wolniejsze
od memcpy. Wariant z wcześniejszym reserve przy sumowaniu
dużych stringów przegrywa bardzo nieznacznie a przy sumowaniu małych
około dwukrotnie.
Fakt, że wariant bez reserve przegrywa jest naturalny, obiekt dokonuje wielokrotnej realokacji bufora z przenoszeniem danych. Jest to zapłata za wygodę (brak konieczności policzenia rozmiaru docelowego bufora).
A czym przegrywa wariant z reserve?
Rzućmy okiem na kod. Po porozwijaniu rozmaitych funkcji inline operator += (w ujęciu biblioteki C++ dołączanej do gcc) jest funkcją inline o treści:
// O tym za moment
_M_check_length(size_type(0), __n, "basic_string::append");
// Ewentualna realokacja
const size_type __len = __n + this->size();
if (__len > this->capacity() || _M_rep()->_M_is_shared())
this->reserve(__len);
// To ostatecznie sprowadza się do memcpy
_M_assign(_M_data() + this->size(), __n, __c);
Środkowy fragment jest sprawdzeniem, czy bufor jest wystarczająco duży (albo czy nie jest współdzielony z innym obiektem). W scenariuszu z wyprzedzającym reserve realokacja nigdy nie jest potrzebna, ponosimy jednak pewien koszt weryfikacji tego faktu.
Zostaje jeszcze trochę dziwacznie wyglądające _M_check_length.
By sprawdzić, co robi, musiałem chwilkę pokopać. Otóż … funkcja ta sprawdza, czy dodanie parametru do aktualnego rozmiaru nie spowoduje przekroczenia maksymalnego dopuszczalnego rozmiaru (a działania są zapisane tak, by nie były podatna na przepełnienia).
Podsumowując, string jest wolniejszy, bo płaci cenę za dokładne zabezpieczenie przed pisaniem poza brzegiem zaalokowanego bufora i za weryfikowanie, czy przy arytmetyce długości nie dochodzi do arytmetycznych przepełnień.
Czyli dokładnie za te sprawy, które gitowa implementacja na memcpy zaniedbała.
I jeszcze o kontekście
Wróćmy jeszcze na moment do oryginalnej funkcji. Jest to formatowanie pełnej nazwy pliku przez jej złożenie z fragmentów. W realnych zastosowaniach (na normalnych a nie złośliwie podsuniętych danych) będzie to tabela kilku-kilkunastu elementów o długości kilka-dwadzieścia parę znaków.
Dla tego typu danych mój mini-benchmark wykonuje 2000000 obrotów w czasie poniżej 0.5 sekundy (na wolnym laptopie, na szybkim PC spada to jeszcze o rząd). Dla pojedynczej operacji potencjalna optymalizacja to czas rzędu 0.1 mikrosekundy. Niechby było to ogromne repo, z 1000 plików. Dla takiego może wyjść łącznie oszczędność 0.0001s.
Do czego mogłoby służyć policzenie tych nazw? Cóż, zapewne albo do wypisania na ekran, albo do użycia jako parametru przy jakiejś funkcji I/O (open, stat itp).
Wypisanie 1000 wierszy na konsolę trwa u mnie ok. 0.03s.
Słynny cytat z dziadka Knutha - o przedwczesnych optymalizacjach - kłania się do ziemi.
Treść benchmarka
Dla kompletu, treść benchmarka. Można by go na wiele sposobów ulepszyć, by był bardziej wiarygodny (wprowadzając trochę alokacji i zwalniania pamięci między wariantami by zaburzyć strukturę alokatorów, dbając o bardziej różnorodny rozkład kopiowanych danych, różnicując reprezentację danych źródłowych…).
#include <cstring>
#include <string>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
using std::chrono::system_clock;
using std::chrono::duration;
//////////////////////////////////////////////////////////////////////
// Testowane procedury (kontrolnie zwracają długość)
//////////////////////////////////////////////////////////////////////
// Proste += na stringach
unsigned
concat_string_simple(const vector<string>& data)
{
string result;
for(const string& item : data)
{
result += item;
result += '/';
}
return result.size();
}
// += na stringach z wcześniejszym reserve
unsigned
concat_string_reserve(const vector<string>& data)
{
string::size_type total = 0;
for(const string& item : data)
{
total += item.size() + 1;
}
string result;
result.reserve(total);
for(const string& item : data)
{
result += item;
result += '/';
}
return result.size();
}
unsigned
concat_memcpy(const vector<string>& data)
{
// total liczę po C++-owemu bo jest to dość analogiczne
// do sumowania atrybutów len z łączonej listy a'la git
string::size_type total = 0;
for(const string& item : data)
{
total += item.size() + 1;
}
char *result = (char*)malloc(total);
char *update = result;
for(const string& item : data)
{
unsigned size = item.size();
memcpy(update, item.data(), size);
update[size] = '/';
update += size + 1;
}
unsigned calc = update - result;
free(result);
return calc;
}
unsigned
concat_strcpy(const vector<string>& data)
{
// Czysto C-owato, strlen i strcpy
string::size_type total = 0;
for(const string& item : data)
{
total += strlen(item.c_str()) + 1;
}
char *result = (char*)malloc(total);
char *update = result;
for(const string& item : data)
{
unsigned size = item.size();
strcpy(update, item.c_str());
update[size] = '/';
update += size + 1;
}
unsigned calc = update - result;
free(result);
return calc;
}
//////////////////////////////////////////////////////////////////////
// Pomocnicze drobiazgi
//////////////////////////////////////////////////////////////////////
void build_sample_data(unsigned count,
unsigned minSize, unsigned maxSize,
vector<string>& output)
{
output.reserve(count);
unsigned currSize = minSize;
unsigned delta = (maxSize - minSize) / count;
if(! delta) {
delta = 1;
}
for(unsigned i = 0; i < count; ++ i) {
output.push_back(string(currSize, 'x'));
currSize += 1;
if(currSize > maxSize) {
currSize = minSize;
}
}
}
void print_result(const string& label, double duration, unsigned ops)
{
cout << " " << left << setw(20) << label + ':' << " "
<< right << fixed << setw(8) << setprecision(5) << duration
<< " s/total"
<< right << fixed << setw(18) << setprecision(5)
<< 1000000 * duration / ops << " us/op"
<< endl;
}
///////////////////////////////////////////////////////////////////////////
// Benchmark
//////////////////////////////////////////////////////////////////////////
typedef unsigned (*ConcatFunction)(const vector<string>& data);
// Zmierzenie pojedynczej funkcji
void benchmark_function(const string& label,
ConcatFunction concat_function,
const vector<string>& sample_data,
unsigned repeats_count)
{
auto before = system_clock::now();
unsigned total = 0; // By nie wyoptymalizował za łatwo
for(unsigned i = 0; i < repeats_count; ++ i) {
total += concat_function(sample_data);
}
duration<double> elapsed = system_clock::now() - before;
print_result(label, elapsed.count(), repeats_count);
}
// Pełny benchmark dla danych podanego rozmiaru
void benchmark(unsigned sample_size,
unsigned min_elem_size, unsigned max_elem_size,
unsigned repeats_count)
{
vector<string> sample_data;
build_sample_data(sample_size, min_elem_size, max_elem_size, sample_data);
// Jednorazowe wykonanie obu wariantów na rozgrzewkę, by szarpnąć ramem
unsigned size1 = concat_string_simple(sample_data);
unsigned size2 = concat_string_reserve(sample_data);
unsigned size3 = concat_memcpy(sample_data);
unsigned size4 = concat_strcpy(sample_data);
if(size1 != size2 || size2 != size3 || size3 != size4) {
cout << "Algo error" << endl;
exit(1);
}
cout << "Suma " << sample_size << " napisow o rozmiarach "
<< min_elem_size << "-" << max_elem_size
<< " (" << "wynik " << size1 << " bajtow). " << repeats_count << " iteracji" << endl;
benchmark_function("string", concat_string_simple,
sample_data, repeats_count);
benchmark_function("string/reserve", concat_string_reserve,
sample_data, repeats_count);
benchmark_function("memcpy", concat_memcpy,
sample_data, repeats_count);
benchmark_function("strcpy", concat_strcpy,
sample_data, repeats_count);
}
int main()
{
benchmark(5, 10, 20, 2000000);
benchmark(5, 17, 16000, 2000000);
benchmark(25, 5, 40, 200000);
benchmark(25, 9999, 29999, 10000);
benchmark(10000, 5, 40, 5000);
benchmark(10000, 2005, 3440, 20);
}
Kompilowałem poleceniem:
c++ -o malloc_vs_string_gcc.exe -O3 --std=c++11 malloc_vs_string.cxx -lrt
(albo analogicznie clangiem, bez istotnych różnic w efektach)
RSS
Feedly
Email
Subskrybuj
