Repository navigation
Expand file tree
/
Copy pathcppsort.tex
More file actions
214 lines (197 loc) · 7.1 KB
/
Copy pathcppsort.tex
File metadata and controls
214 lines (197 loc) · 7.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
%% -*- coding:utf-8 -*-
\documentclass[14pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{minted}
\usepackage{longtable}
\usepackage{hyperref}
\hypersetup{
pdftex,
allcolors=blue,
bookmarksnumbered=true,
bookmarksopen=true,
bookmarksopenlevel=1,
colorlinks=true,
pdfstartview=Fit,
pdfpagemode=UseOutlines,
pdfpagelayout=TwoPageRight,
pdftitle={Inside STL sort algorithm},
pdfsubject={STL sort},
pdfauthor={Ivan Murashkо},
pdfkeywords={STL, C++, quick sort}
}
\title{Inside STL sort algorithm}
\author{Ivan Murashko}
\date{}
\begin{document}
\maketitle
\section*{Introduction}
One of the trickiest thing in C++ is an error catch. Most part of errors
are located on the application level and you can be quite sure that
the library, especially the well known STL, is error free. But what
should you do if your application code is trivial i.e. it seems to be
error free but you get a SIGSEGV inside a system library. Most
probably you just fell into a situation that is described in the
article.
Note: All examples in the article use gcc 7.4.0 from the docker image
gcc:7:
\begin{minted}{shell}
docker run gcc:7 gcc --version
gcc (GCC) 7.4.0
\end{minted}
The source code for examples can be found on the article git
repository \cite{github:cppsort_ivanmurashko} in the folder
\textbf{cppsort/src}.
\section{Example}
Lets look at the following code:
\inputminted{c++}{./src/sort.cpp}
What output does it produce? One can expect the following one:
\begin{minted}{shell}
$ docker run -v "$PWD":/tmp/test -w /tmp/test gcc:7 ./src/sort
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$
\end{minted}
i.e. the original array has to be displayed. In reality the following
output will be produced by gcc 7.4.0
\begin{minted}{shell}
$ docker run -v "$PWD":/tmp/test -w /tmp/test gcc:7 ./src/sort
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$
\end{minted}
As one can see the array is broken. How it can happen if every
function in the code snapshot seems to be correct? The answer is
below.
\section{Inside STL sort}
The STL library states the following requirements for \textbf{std::sort}
\cite{ISO:2013:IIP}(pp. 897-898): the compare function must follow so
called strict weak ordering requirement. Especially it
says that
\begin{minted}{c++}
comp(x, x) == false;
\end{minted}
The requirement is violated
by the $\le$ operand used in our example.
Why the requirement is so important? The answer is in the algorithm
that is used for sorting. STL uses an optimized version of Quicksort algorithm
\cite{wiki:quicksort}.
The code that produces the problem can be found via the following command
\begin{minted}{shell}
docker run gcc:7 tail -n +1893 \
/usr/local/include/c++/7.4.0/bits/stl_algo.h | head -n 21
\end{minted}
and looks as follow
\begin{minted}{c++}
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_RandomAccessIterator __pivot, _Compare __comp)
{
while (true)
{
while (__comp(__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, __last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
\end{minted}
As soon as our example has all elements equal to 1 one can assume
that \textbf{\_\_pivot} also keeps $1$. In the function we start to
compare all elements with the pivot. The used comparator will always
produce \textbf{true} as soon
as $1 \le 1$. The size of the array is 17
\begin{minted}{shell}
(gdb) p data.size()
$1 = 17
\end{minted}
and when we pass through whole array and reach its end we
will find $0$ on the last position (\textbf{\_\_last}), i.e. 18th
element of the array:
\begin{minted}{shell}
(gdb) p *(&data[0] + 17)
$2 = 0
\end{minted}
The found element, that is located outside the array, will be
included into the search as soon as it also satisfies the required
property: $0 \le 1$. The next element will be greater:
\begin{minted}{shell}
(gdb) p *(&data[0] + 18)
$3 = 61777
\end{minted}
The element is 19th element of the array and is located 1 position
after the original \textbf{\_\_last} iterator. Thus the \textbf{\_\_first}
iterator will be 1 position behind the original \textbf{\_\_last} one.
The value will be returned into the following helper
function
\begin{minted}{c++}
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
__comp);
return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}
\end{minted}
that will return the result as \textbf{\_\_cut} in
\begin{minted}{c++}
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
\end{minted}
The \textbf{\_\_last} iterator will be replaced with \textbf{\_\_cut}
that is \textbf{\_\_first + 18} or \textbf{\_\_last + 1}. The range
stays stable until \textbf{\_\_depth\_limit} becomes 0.
Thus \textbf{std::\_\_partial\_sort} will get the range for sort that is
greater (by 1) then original one. The element ($0$) outside
array will be placed into beginning for the vector as
\textbf{std::\_\_partial\_sort}'s application result.
\section*{Conclusion}
As you can see, the comparator that violates strict weak ordering
requirements will lead to array boundary condition violations. In our
example we were ``lucky'' and just got incorrect data in the result. The
SIGSEGV is more probable obvious result for such error.
\footnote{
In real life the broken data is more probable but often
are not recognized as an error because the result is hidden compare to
SIGSEGV one that is visible immediately.
}
The error can be easily
fixed by using correct comparator, for instance the following one
\begin{minted}{c++}
auto comp = [](int i1, int i2) { return i1 < i2; };
\end{minted}
The example shown in the article demonstrates the importance of
requirements specified as C++ standard. Everyone who does not follow
the requirements during an application development is in the risk of
serious trouble with the application's undefined behaviour.
\bibliographystyle{gost780s}
\bibliography{cppsort}
\end{document}