1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "base/metrics/field_trial.h"
6
7#include <algorithm>
8
9#include "base/build_time.h"
10#include "base/logging.h"
11#include "base/rand_util.h"
12#include "base/sha1.h"
13#include "base/strings/string_util.h"
14#include "base/strings/stringprintf.h"
15#include "base/strings/utf_string_conversions.h"
16#include "base/sys_byteorder.h"
17
18namespace base {
19
20namespace {
21
22// Created a time value based on |year|, |month| and |day_of_month| parameters.
23Time CreateTimeFromParams(int year, int month, int day_of_month) {
24  DCHECK_GT(year, 1970);
25  DCHECK_GT(month, 0);
26  DCHECK_LT(month, 13);
27  DCHECK_GT(day_of_month, 0);
28  DCHECK_LT(day_of_month, 32);
29
30  Time::Exploded exploded;
31  exploded.year = year;
32  exploded.month = month;
33  exploded.day_of_week = 0;  // Should be unused.
34  exploded.day_of_month = day_of_month;
35  exploded.hour = 0;
36  exploded.minute = 0;
37  exploded.second = 0;
38  exploded.millisecond = 0;
39
40  return Time::FromLocalExploded(exploded);
41}
42
43// Returns the boundary value for comparing against the FieldTrial's added
44// groups for a given |divisor| (total probability) and |entropy_value|.
45FieldTrial::Probability GetGroupBoundaryValue(
46    FieldTrial::Probability divisor,
47    double entropy_value) {
48  // Add a tiny epsilon value to get consistent results when converting floating
49  // points to int. Without it, boundary values have inconsistent results, e.g.:
50  //
51  //   static_cast<FieldTrial::Probability>(100 * 0.56) == 56
52  //   static_cast<FieldTrial::Probability>(100 * 0.57) == 56
53  //   static_cast<FieldTrial::Probability>(100 * 0.58) == 57
54  //   static_cast<FieldTrial::Probability>(100 * 0.59) == 59
55  const double kEpsilon = 1e-8;
56  const FieldTrial::Probability result =
57      static_cast<FieldTrial::Probability>(divisor * entropy_value + kEpsilon);
58  // Ensure that adding the epsilon still results in a value < |divisor|.
59  return std::min(result, divisor - 1);
60}
61
62}  // namespace
63
64// statics
65const int FieldTrial::kNotFinalized = -1;
66const int FieldTrial::kDefaultGroupNumber = 0;
67bool FieldTrial::enable_benchmarking_ = false;
68
69const char FieldTrialList::kPersistentStringSeparator('/');
70int FieldTrialList::kNoExpirationYear = 0;
71
72//------------------------------------------------------------------------------
73// FieldTrial methods and members.
74
75FieldTrial::EntropyProvider::~EntropyProvider() {
76}
77
78void FieldTrial::Disable() {
79  DCHECK(!group_reported_);
80  enable_field_trial_ = false;
81
82  // In case we are disabled after initialization, we need to switch
83  // the trial to the default group.
84  if (group_ != kNotFinalized) {
85    // Only reset when not already the default group, because in case we were
86    // forced to the default group, the group number may not be
87    // kDefaultGroupNumber, so we should keep it as is.
88    if (group_name_ != default_group_name_)
89      SetGroupChoice(default_group_name_, kDefaultGroupNumber);
90  }
91}
92
93int FieldTrial::AppendGroup(const std::string& name,
94                            Probability group_probability) {
95  // When the group choice was previously forced, we only need to return the
96  // the id of the chosen group, and anything can be returned for the others.
97  if (forced_) {
98    DCHECK(!group_name_.empty());
99    if (name == group_name_) {
100      // Note that while |group_| may be equal to |kDefaultGroupNumber| on the
101      // forced trial, it will not have the same value as the default group
102      // number returned from the non-forced |FactoryGetFieldTrial()| call,
103      // which takes care to ensure that this does not happen.
104      return group_;
105    }
106    DCHECK_NE(next_group_number_, group_);
107    // We still return different numbers each time, in case some caller need
108    // them to be different.
109    return next_group_number_++;
110  }
111
112  DCHECK_LE(group_probability, divisor_);
113  DCHECK_GE(group_probability, 0);
114
115  if (enable_benchmarking_ || !enable_field_trial_)
116    group_probability = 0;
117
118  accumulated_group_probability_ += group_probability;
119
120  DCHECK_LE(accumulated_group_probability_, divisor_);
121  if (group_ == kNotFinalized && accumulated_group_probability_ > random_) {
122    // This is the group that crossed the random line, so we do the assignment.
123    SetGroupChoice(name, next_group_number_);
124  }
125  return next_group_number_++;
126}
127
128int FieldTrial::group() {
129  FinalizeGroupChoice();
130  if (trial_registered_)
131    FieldTrialList::NotifyFieldTrialGroupSelection(this);
132  return group_;
133}
134
135const std::string& FieldTrial::group_name() {
136  // Call |group()| to ensure group gets assigned and observers are notified.
137  group();
138  DCHECK(!group_name_.empty());
139  return group_name_;
140}
141
142void FieldTrial::SetForced() {
143  // We might have been forced before (e.g., by CreateFieldTrial) and it's
144  // first come first served, e.g., command line switch has precedence.
145  if (forced_)
146    return;
147
148  // And we must finalize the group choice before we mark ourselves as forced.
149  FinalizeGroupChoice();
150  forced_ = true;
151}
152
153// static
154void FieldTrial::EnableBenchmarking() {
155  DCHECK_EQ(0u, FieldTrialList::GetFieldTrialCount());
156  enable_benchmarking_ = true;
157}
158
159// static
160FieldTrial* FieldTrial::CreateSimulatedFieldTrial(
161    const std::string& trial_name,
162    Probability total_probability,
163    const std::string& default_group_name,
164    double entropy_value) {
165  return new FieldTrial(trial_name, total_probability, default_group_name,
166                        entropy_value);
167}
168
169FieldTrial::FieldTrial(const std::string& trial_name,
170                       const Probability total_probability,
171                       const std::string& default_group_name,
172                       double entropy_value)
173    : trial_name_(trial_name),
174      divisor_(total_probability),
175      default_group_name_(default_group_name),
176      random_(GetGroupBoundaryValue(total_probability, entropy_value)),
177      accumulated_group_probability_(0),
178      next_group_number_(kDefaultGroupNumber + 1),
179      group_(kNotFinalized),
180      enable_field_trial_(true),
181      forced_(false),
182      group_reported_(false),
183      trial_registered_(false) {
184  DCHECK_GT(total_probability, 0);
185  DCHECK(!trial_name_.empty());
186  DCHECK(!default_group_name_.empty());
187}
188
189FieldTrial::~FieldTrial() {}
190
191void FieldTrial::SetTrialRegistered() {
192  DCHECK_EQ(kNotFinalized, group_);
193  DCHECK(!trial_registered_);
194  trial_registered_ = true;
195}
196
197void FieldTrial::SetGroupChoice(const std::string& group_name, int number) {
198  group_ = number;
199  if (group_name.empty())
200    StringAppendF(&group_name_, "%d", group_);
201  else
202    group_name_ = group_name;
203  DVLOG(1) << "Field trial: " << trial_name_ << " Group choice:" << group_name_;
204}
205
206void FieldTrial::FinalizeGroupChoice() {
207  if (group_ != kNotFinalized)
208    return;
209  accumulated_group_probability_ = divisor_;
210  // Here it's OK to use |kDefaultGroupNumber| since we can't be forced and not
211  // finalized.
212  DCHECK(!forced_);
213  SetGroupChoice(default_group_name_, kDefaultGroupNumber);
214}
215
216bool FieldTrial::GetActiveGroup(ActiveGroup* active_group) const {
217  if (!group_reported_ || !enable_field_trial_)
218    return false;
219  DCHECK_NE(group_, kNotFinalized);
220  active_group->trial_name = trial_name_;
221  active_group->group_name = group_name_;
222  return true;
223}
224
225//------------------------------------------------------------------------------
226// FieldTrialList methods and members.
227
228// static
229FieldTrialList* FieldTrialList::global_ = NULL;
230
231// static
232bool FieldTrialList::used_without_global_ = false;
233
234FieldTrialList::Observer::~Observer() {
235}
236
237FieldTrialList::FieldTrialList(
238    const FieldTrial::EntropyProvider* entropy_provider)
239    : entropy_provider_(entropy_provider),
240      observer_list_(new ObserverListThreadSafe<FieldTrialList::Observer>(
241          ObserverListBase<FieldTrialList::Observer>::NOTIFY_EXISTING_ONLY)) {
242  DCHECK(!global_);
243  DCHECK(!used_without_global_);
244  global_ = this;
245
246  Time two_years_from_build_time = GetBuildTime() + TimeDelta::FromDays(730);
247  Time::Exploded exploded;
248  two_years_from_build_time.LocalExplode(&exploded);
249  kNoExpirationYear = exploded.year;
250}
251
252FieldTrialList::~FieldTrialList() {
253  AutoLock auto_lock(lock_);
254  while (!registered_.empty()) {
255    RegistrationMap::iterator it = registered_.begin();
256    it->second->Release();
257    registered_.erase(it->first);
258  }
259  DCHECK_EQ(this, global_);
260  global_ = NULL;
261}
262
263// static
264FieldTrial* FieldTrialList::FactoryGetFieldTrial(
265    const std::string& trial_name,
266    FieldTrial::Probability total_probability,
267    const std::string& default_group_name,
268    const int year,
269    const int month,
270    const int day_of_month,
271    FieldTrial::RandomizationType randomization_type,
272    int* default_group_number) {
273  return FactoryGetFieldTrialWithRandomizationSeed(
274      trial_name, total_probability, default_group_name,
275      year, month, day_of_month, randomization_type, 0, default_group_number);
276}
277
278// static
279FieldTrial* FieldTrialList::FactoryGetFieldTrialWithRandomizationSeed(
280    const std::string& trial_name,
281    FieldTrial::Probability total_probability,
282    const std::string& default_group_name,
283    const int year,
284    const int month,
285    const int day_of_month,
286    FieldTrial::RandomizationType randomization_type,
287    uint32 randomization_seed,
288    int* default_group_number) {
289  if (default_group_number)
290    *default_group_number = FieldTrial::kDefaultGroupNumber;
291  // Check if the field trial has already been created in some other way.
292  FieldTrial* existing_trial = Find(trial_name);
293  if (existing_trial) {
294    CHECK(existing_trial->forced_);
295    // If the default group name differs between the existing forced trial
296    // and this trial, then use a different value for the default group number.
297    if (default_group_number &&
298        default_group_name != existing_trial->default_group_name()) {
299      // If the new default group number corresponds to the group that was
300      // chosen for the forced trial (which has been finalized when it was
301      // forced), then set the default group number to that.
302      if (default_group_name == existing_trial->group_name_internal()) {
303        *default_group_number = existing_trial->group_;
304      } else {
305        // Otherwise, use |kNonConflictingGroupNumber| (-2) for the default
306        // group number, so that it does not conflict with the |AppendGroup()|
307        // result for the chosen group.
308        const int kNonConflictingGroupNumber = -2;
309        COMPILE_ASSERT(
310            kNonConflictingGroupNumber != FieldTrial::kDefaultGroupNumber,
311            conflicting_default_group_number);
312        COMPILE_ASSERT(
313            kNonConflictingGroupNumber != FieldTrial::kNotFinalized,
314            conflicting_default_group_number);
315        *default_group_number = kNonConflictingGroupNumber;
316      }
317    }
318    return existing_trial;
319  }
320
321  double entropy_value;
322  if (randomization_type == FieldTrial::ONE_TIME_RANDOMIZED) {
323    entropy_value = GetEntropyProviderForOneTimeRandomization()->
324          GetEntropyForTrial(trial_name, randomization_seed);
325  } else {
326    DCHECK_EQ(FieldTrial::SESSION_RANDOMIZED, randomization_type);
327    DCHECK_EQ(0U, randomization_seed);
328    entropy_value = RandDouble();
329  }
330
331  FieldTrial* field_trial = new FieldTrial(trial_name, total_probability,
332                                           default_group_name, entropy_value);
333  if (GetBuildTime() > CreateTimeFromParams(year, month, day_of_month))
334    field_trial->Disable();
335  FieldTrialList::Register(field_trial);
336  return field_trial;
337}
338
339// static
340FieldTrial* FieldTrialList::Find(const std::string& name) {
341  if (!global_)
342    return NULL;
343  AutoLock auto_lock(global_->lock_);
344  return global_->PreLockedFind(name);
345}
346
347// static
348int FieldTrialList::FindValue(const std::string& name) {
349  FieldTrial* field_trial = Find(name);
350  if (field_trial)
351    return field_trial->group();
352  return FieldTrial::kNotFinalized;
353}
354
355// static
356std::string FieldTrialList::FindFullName(const std::string& name) {
357  FieldTrial* field_trial = Find(name);
358  if (field_trial)
359    return field_trial->group_name();
360  return std::string();
361}
362
363// static
364bool FieldTrialList::TrialExists(const std::string& name) {
365  return Find(name) != NULL;
366}
367
368// static
369void FieldTrialList::StatesToString(std::string* output) {
370  FieldTrial::ActiveGroups active_groups;
371  GetActiveFieldTrialGroups(&active_groups);
372  for (FieldTrial::ActiveGroups::const_iterator it = active_groups.begin();
373       it != active_groups.end(); ++it) {
374    DCHECK_EQ(std::string::npos,
375              it->trial_name.find(kPersistentStringSeparator));
376    DCHECK_EQ(std::string::npos,
377              it->group_name.find(kPersistentStringSeparator));
378    output->append(it->trial_name);
379    output->append(1, kPersistentStringSeparator);
380    output->append(it->group_name);
381    output->append(1, kPersistentStringSeparator);
382  }
383}
384
385// static
386void FieldTrialList::GetActiveFieldTrialGroups(
387    FieldTrial::ActiveGroups* active_groups) {
388  DCHECK(active_groups->empty());
389  if (!global_)
390    return;
391  AutoLock auto_lock(global_->lock_);
392
393  for (RegistrationMap::iterator it = global_->registered_.begin();
394       it != global_->registered_.end(); ++it) {
395    FieldTrial::ActiveGroup active_group;
396    if (it->second->GetActiveGroup(&active_group))
397      active_groups->push_back(active_group);
398  }
399}
400
401// static
402bool FieldTrialList::CreateTrialsFromString(
403    const std::string& trials_string,
404    FieldTrialActivationMode mode,
405    const std::set<std::string>& ignored_trial_names) {
406  DCHECK(global_);
407  if (trials_string.empty() || !global_)
408    return true;
409
410  size_t next_item = 0;
411  while (next_item < trials_string.length()) {
412    size_t name_end = trials_string.find(kPersistentStringSeparator, next_item);
413    if (name_end == trials_string.npos || next_item == name_end)
414      return false;
415    size_t group_name_end = trials_string.find(kPersistentStringSeparator,
416                                               name_end + 1);
417    if (group_name_end == trials_string.npos || name_end + 1 == group_name_end)
418      return false;
419    std::string name(trials_string, next_item, name_end - next_item);
420    std::string group_name(trials_string, name_end + 1,
421                           group_name_end - name_end - 1);
422    next_item = group_name_end + 1;
423
424    if (ignored_trial_names.find(name) != ignored_trial_names.end())
425      continue;
426
427    FieldTrial* trial = CreateFieldTrial(name, group_name);
428    if (!trial)
429      return false;
430    if (mode == ACTIVATE_TRIALS) {
431      // Call |group()| to mark the trial as "used" and notify observers, if
432      // any. This is useful to ensure that field trials created in child
433      // processes are properly reported in crash reports.
434      trial->group();
435    }
436  }
437  return true;
438}
439
440// static
441FieldTrial* FieldTrialList::CreateFieldTrial(
442    const std::string& name,
443    const std::string& group_name) {
444  DCHECK(global_);
445  DCHECK_GE(name.size(), 0u);
446  DCHECK_GE(group_name.size(), 0u);
447  if (name.empty() || group_name.empty() || !global_)
448    return NULL;
449
450  FieldTrial* field_trial = FieldTrialList::Find(name);
451  if (field_trial) {
452    // In single process mode, or when we force them from the command line,
453    // we may have already created the field trial.
454    if (field_trial->group_name_internal() != group_name)
455      return NULL;
456    return field_trial;
457  }
458  const int kTotalProbability = 100;
459  field_trial = new FieldTrial(name, kTotalProbability, group_name, 0);
460  FieldTrialList::Register(field_trial);
461  // Force the trial, which will also finalize the group choice.
462  field_trial->SetForced();
463  return field_trial;
464}
465
466// static
467void FieldTrialList::AddObserver(Observer* observer) {
468  if (!global_)
469    return;
470  global_->observer_list_->AddObserver(observer);
471}
472
473// static
474void FieldTrialList::RemoveObserver(Observer* observer) {
475  if (!global_)
476    return;
477  global_->observer_list_->RemoveObserver(observer);
478}
479
480// static
481void FieldTrialList::NotifyFieldTrialGroupSelection(FieldTrial* field_trial) {
482  if (!global_)
483    return;
484
485  {
486    AutoLock auto_lock(global_->lock_);
487    if (field_trial->group_reported_)
488      return;
489    field_trial->group_reported_ = true;
490  }
491
492  if (!field_trial->enable_field_trial_)
493    return;
494
495  global_->observer_list_->Notify(
496      &FieldTrialList::Observer::OnFieldTrialGroupFinalized,
497      field_trial->trial_name(),
498      field_trial->group_name_internal());
499}
500
501// static
502size_t FieldTrialList::GetFieldTrialCount() {
503  if (!global_)
504    return 0;
505  AutoLock auto_lock(global_->lock_);
506  return global_->registered_.size();
507}
508
509// static
510const FieldTrial::EntropyProvider*
511    FieldTrialList::GetEntropyProviderForOneTimeRandomization() {
512  if (!global_) {
513    used_without_global_ = true;
514    return NULL;
515  }
516
517  return global_->entropy_provider_.get();
518}
519
520FieldTrial* FieldTrialList::PreLockedFind(const std::string& name) {
521  RegistrationMap::iterator it = registered_.find(name);
522  if (registered_.end() == it)
523    return NULL;
524  return it->second;
525}
526
527// static
528void FieldTrialList::Register(FieldTrial* trial) {
529  if (!global_) {
530    used_without_global_ = true;
531    return;
532  }
533  AutoLock auto_lock(global_->lock_);
534  DCHECK(!global_->PreLockedFind(trial->trial_name()));
535  trial->AddRef();
536  trial->SetTrialRegistered();
537  global_->registered_[trial->trial_name()] = trial;
538}
539
540}  // namespace base
541