1/* Copyright (C) 2007 MySQL AB, Sergei Golubchik & Michael Widenius
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
15
16/*
17 implements Universal Unique Identifiers (UUIDs), as in
18 DCE 1.1: Remote Procedure Call,
19 Open Group Technical Standard Document Number C706, October 1997,
20 (supersedes C309 DCE: Remote Procedure Call 8/1994,
21 which was basis for ISO/IEC 11578:1996 specification)
22
23 A UUID has the following structure:
24
25 Field NDR Data Type Octet # Note
26 time_low unsigned long 0-3 The low field of the
27 timestamp.
28 time_mid unsigned short 4-5 The middle field of
29 the timestamp.
30 time_hi_and_version unsigned short 6-7 The high field of the
31 timestamp multiplexed
32 with the version number.
33 clock_seq_hi_and_reserved unsigned small 8 The high field of the
34 clock sequence multi-
35 plexed with the variant.
36 clock_seq_low unsigned small 9 The low field of the
37 clock sequence.
38 node character 10-15 The spatially unique node
39 identifier.
40*/
41
42#include "mysys_priv.h"
43#include <my_rnd.h>
44#include <m_string.h>
45#include <myisampack.h> /* mi_int2store, mi_int4store */
46
47static my_bool my_uuid_inited= 0;
48static struct my_rnd_struct uuid_rand;
49static uint nanoseq;
50static ulonglong uuid_time= 0;
51static longlong interval_timer_offset;
52static uchar uuid_suffix[2+6]; /* clock_seq and node */
53
54static mysql_mutex_t LOCK_uuid_generator;
55
56/*
57 Number of 100-nanosecond intervals between
58 1582-10-15 00:00:00.00 and 1970-01-01 00:00:00.00
59*/
60
61#define UUID_TIME_OFFSET ((ulonglong) 141427 * 24 * 60 * 60 * \
62 1000 * 1000 * 10)
63#define UUID_VERSION 0x1000
64#define UUID_VARIANT 0x8000
65
66
67/* Helper function */
68
69static void set_clock_seq()
70{
71 uint16 clock_seq= ((uint)(my_rnd(&uuid_rand)*16383)) | UUID_VARIANT;
72 mi_int2store(uuid_suffix, clock_seq);
73 interval_timer_offset= (my_hrtime().val * 10 - my_interval_timer()/100 +
74 UUID_TIME_OFFSET);
75}
76
77
78/**
79 Init structures needed for my_uuid
80
81 @func my_uuid_init()
82 @param seed1 Seed for random generator
83 @param seed2 Seed for random generator
84
85 @note
86 Seed1 & seed2 should NOT depend on clock. This is to be able to
87 generate a random mac address according to UUID specs.
88*/
89
90void my_uuid_init(ulong seed1, ulong seed2)
91{
92 uchar *mac= uuid_suffix+2;
93 ulonglong now;
94
95 if (my_uuid_inited)
96 return;
97 my_uuid_inited= 1;
98 now= my_interval_timer()/100 + interval_timer_offset;
99 nanoseq= 0;
100
101 if (my_gethwaddr(mac))
102 {
103 uint i;
104 /*
105 Generating random "hardware addr"
106
107 Specs explicitly specify that node identifier should NOT
108 correlate with a clock_seq value, so we use a separate
109 randominit() here.
110 */
111 /* purecov: begin inspected */
112 my_rnd_init(&uuid_rand, (ulong) (seed2+ now/2), (ulong) (now+rand()));
113 for (i=0; i < array_elements(uuid_suffix) -2 ; i++)
114 mac[i]= (uchar)(my_rnd(&uuid_rand)*255);
115 /* purecov: end */
116 }
117 my_rnd_init(&uuid_rand, (ulong) (seed1 + now), (ulong) (now/2+ getpid()));
118 set_clock_seq();
119 mysql_mutex_init(key_LOCK_uuid_generator, &LOCK_uuid_generator, MY_MUTEX_INIT_FAST);
120}
121
122
123/**
124 Create a global unique identifier (uuid)
125
126 @func my_uuid()
127 @param to Store uuid here. Must be of size MY_UUID_SIZE (16)
128*/
129
130void my_uuid(uchar *to)
131{
132 ulonglong tv;
133 uint32 time_low;
134 uint16 time_mid, time_hi_and_version;
135
136 DBUG_ASSERT(my_uuid_inited);
137
138 mysql_mutex_lock(&LOCK_uuid_generator);
139 tv= my_interval_timer()/100 + interval_timer_offset + nanoseq;
140
141 if (likely(tv > uuid_time))
142 {
143 /*
144 Current time is ahead of last timestamp, as it should be.
145 If we "borrowed time", give it back, just as long as we
146 stay ahead of the previous timestamp.
147 */
148 if (nanoseq)
149 {
150 ulong delta;
151 DBUG_ASSERT((tv > uuid_time) && (nanoseq > 0));
152 /*
153 -1 so we won't make tv= uuid_time for nanoseq >= (tv - uuid_time)
154 */
155 delta= MY_MIN(nanoseq, (ulong)(tv - uuid_time -1));
156 tv-= delta;
157 nanoseq-= delta;
158 }
159 }
160 else
161 {
162 if (unlikely(tv == uuid_time))
163 {
164 /*
165 For low-res system clocks. If several requests for UUIDs
166 end up on the same tick, we add a nano-second to make them
167 different.
168 ( current_timestamp + nanoseq * calls_in_this_period )
169 may end up > next_timestamp; this is OK. Nonetheless, we'll
170 try to unwind nanoseq when we get a chance to.
171 If nanoseq overflows, we'll start over with a new numberspace
172 (so the if() below is needed so we can avoid the ++tv and thus
173 match the follow-up if() if nanoseq overflows!).
174 */
175 if (likely(++nanoseq))
176 ++tv;
177 }
178
179 if (unlikely(tv <= uuid_time))
180 {
181 /*
182 If the admin changes the system clock (or due to Daylight
183 Saving Time), the system clock may be turned *back* so we
184 go through a period once more for which we already gave out
185 UUIDs. To avoid duplicate UUIDs despite potentially identical
186 times, we make a new random component.
187 We also come here if the nanoseq "borrowing" overflows.
188 In either case, we throw away any nanoseq borrowing since it's
189 irrelevant in the new numberspace.
190 */
191 set_clock_seq();
192 tv= my_interval_timer()/100 + interval_timer_offset;
193 nanoseq= 0;
194 DBUG_PRINT("uuid",("making new numberspace"));
195 }
196 }
197
198 uuid_time=tv;
199 mysql_mutex_unlock(&LOCK_uuid_generator);
200
201 time_low= (uint32) (tv & 0xFFFFFFFF);
202 time_mid= (uint16) ((tv >> 32) & 0xFFFF);
203 time_hi_and_version= (uint16) ((tv >> 48) | UUID_VERSION);
204
205 /*
206 Note, that the standard does NOT specify byte ordering in
207 multi-byte fields. it's implementation defined (but must be
208 the same for all fields).
209 We use big-endian, so we can use memcmp() to compare UUIDs
210 and for straightforward UUID to string conversion.
211 */
212 mi_int4store(to, time_low);
213 mi_int2store(to+4, time_mid);
214 mi_int2store(to+6, time_hi_and_version);
215 bmove(to+8, uuid_suffix, sizeof(uuid_suffix));
216}
217
218
219/**
220 Convert uuid to string representation
221
222 @func my_uuid2str()
223 @param guid uuid
224 @param s Output buffer.Must be at least MY_UUID_STRING_LENGTH+1 large.
225*/
226void my_uuid2str(const uchar *guid, char *s)
227{
228 int i;
229 for (i=0; i < MY_UUID_SIZE; i++)
230 {
231 *s++= _dig_vec_lower[guid[i] >>4];
232 *s++= _dig_vec_lower[guid[i] & 15];
233 /* Set '-' at intervals 3, 5, 7 and 9 */
234 if ((1 << i) & ((1 << 3) | (1 << 5) | (1 << 7) | (1 << 9)))
235 *s++= '-';
236 }
237}
238
239void my_uuid_end()
240{
241 if (my_uuid_inited)
242 {
243 my_uuid_inited= 0;
244 mysql_mutex_destroy(&LOCK_uuid_generator);
245 }
246}
247