--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -5075,16 +5075,42 @@
     "kind": "count",
     "description": "a testing histogram; not meant to be touched"
   },
   "TELEMETRY_TEST_COUNT_INIT_NO_RECORD": {
     "expires_in_version": "never",
     "kind": "count",
     "description": "a testing histogram; not meant to be touched - initially not recording"
   },
+  "TELEMETRY_TEST_CATEGORICAL": {
+    "alert_emails": ["telemetry-client-dev@mozilla.com"],
+    "bug_numbers": [1188888],
+    "expires_in_version": "never",
+    "kind": "categorical",
+    "labels": [
+      "CommonLabel",
+      "Label2",
+      "Label3"
+    ],
+    "description": "a testing histogram; not meant to be touched"
+  },
+  "TELEMETRY_TEST_CATEGORICAL_OPTOUT": {
+    "alert_emails": ["telemetry-client-dev@mozilla.com"],
+    "bug_numbers": [1188888],
+    "expires_in_version": "never",
+    "releaseChannelCollection": "opt-out",
+    "kind": "categorical",
+    "labels": [
+      "CommonLabel",
+      "Label4",
+      "Label5",
+      "Label6"
+    ],
+    "description": "a testing histogram; not meant to be touched"
+  },
   "TELEMETRY_TEST_KEYED_COUNT_INIT_NO_RECORD": {
     "expires_in_version": "never",
     "kind": "count",
     "keyed": true,
     "description": "a testing histogram; not meant to be touched - initially not recording"
   },
   "TELEMETRY_TEST_KEYED_FLAG": {
     "expires_in_version": "never",

--- a/toolkit/components/telemetry/TelemetryHistogram.cpp
+++ b/toolkit/components/telemetry/TelemetryHistogram.cpp
@@ -114,20 +114,23 @@ typedef nsClassHashtable<nsCStringHashKe
 struct HistogramInfo {
   uint32_t min;
   uint32_t max;
   uint32_t bucketCount;
   uint32_t histogramType;
   uint32_t id_offset;
   uint32_t expiration_offset;
   uint32_t dataset;
+  uint32_t label_index;
+  uint32_t label_count;
   bool keyed;
 
   const char *id() const;
   const char *expiration() const;
+  nsresult label_id(const char* label, uint32_t* labelId) const;
 };
 
 struct AddonHistogramInfo {
   uint32_t min;
   uint32_t max;
   uint32_t bucketCount;
   uint32_t histogramType;
   Histogram *h;
@@ -284,16 +287,41 @@ HistogramInfo::id() const
 }
 
 const char *
 HistogramInfo::expiration() const
 {
   return &gHistogramStringTable[this->expiration_offset];
 }
 
+nsresult
+HistogramInfo::label_id(const char* label, uint32_t* labelId) const
+{
+  MOZ_ASSERT(label);
+  MOZ_ASSERT(this->histogramType == nsITelemetry::HISTOGRAM_CATEGORICAL);
+  if (this->histogramType != nsITelemetry::HISTOGRAM_CATEGORICAL) {
+    return NS_ERROR_FAILURE;
+  }
+
+  for (uint32_t i = 0; i < this->label_count; ++i) {
+    // gHistogramLabelTable contains the indices of the label strings in the
+    // gHistogramStringTable.
+    // They are stored in-order and consecutively, from the offset label_index
+    // to (label_index + label_count).
+    uint32_t string_offset = gHistogramLabelTable[this->label_index + i];
+    const char* const str = &gHistogramStringTable[string_offset];
+    if (::strcmp(label, str) == 0) {
+      *labelId = i;
+      return NS_OK;
+    }
+  }
+
+  return NS_ERROR_FAILURE;
+}
+
 } // namespace
 
 
 ////////////////////////////////////////////////////////////////////////
 ////////////////////////////////////////////////////////////////////////
 //
 // PRIVATE: Histogram Get, Add, Clone, Clear functions
 
@@ -349,16 +377,17 @@ internal_HistogramGet(const char *name, 
     histogramType = nsITelemetry::HISTOGRAM_LINEAR;
   }
 
   switch (histogramType) {
   case nsITelemetry::HISTOGRAM_EXPONENTIAL:
     *result = Histogram::FactoryGet(name, min, max, bucketCount, Histogram::kUmaTargetedHistogramFlag);
     break;
   case nsITelemetry::HISTOGRAM_LINEAR:
+  case nsITelemetry::HISTOGRAM_CATEGORICAL:
     *result = LinearHistogram::FactoryGet(name, min, max, bucketCount, Histogram::kUmaTargetedHistogramFlag);
     break;
   case nsITelemetry::HISTOGRAM_BOOLEAN:
     *result = BooleanHistogram::FactoryGet(name, Histogram::kUmaTargetedHistogramFlag);
     break;
   case nsITelemetry::HISTOGRAM_FLAG:
     *result = FlagHistogram::FactoryGet(name, Histogram::kUmaTargetedHistogramFlag);
     break;
@@ -1042,49 +1071,78 @@ internal_GetKeyedHistogramById(const nsA
 // that seems preferable to risking deadlock.
 
 namespace {
 
 bool
 internal_JSHistogram_Add(JSContext *cx, unsigned argc, JS::Value *vp)
 {
   JSObject *obj = JS_THIS_OBJECT(cx, vp);
+  MOZ_ASSERT(obj);
   if (!obj) {
     return false;
   }
 
   Histogram *h = static_cast<Histogram*>(JS_GetPrivate(obj));
   MOZ_ASSERT(h);
   Histogram::ClassType type = h->histogram_type();
 
   JS::CallArgs args = CallArgsFromVp(argc, vp);
 
+  if (!internal_CanRecordBase()) {
+    return true;
+  }
+
   // If we don't have an argument for the count histogram, assume an increment of 1.
   // Otherwise, make sure to run some sanity checks on the argument.
-  int32_t value = 1;
-  if ((type != base::CountHistogram::COUNT_HISTOGRAM) || args.length()) {
-    if (!args.length()) {
-      JS_ReportError(cx, "Expected one argument");
+  if ((type == base::CountHistogram::COUNT_HISTOGRAM) && (args.length() == 0)) {
+    internal_HistogramAdd(*h, 1);
+    return true;
+  }
+
+  // For categorical histograms we allow passing a string argument that specifies the label.
+  mozilla::Telemetry::ID id;
+  if (type == base::LinearHistogram::LINEAR_HISTOGRAM &&
+      (args.length() > 0) && args[0].isString() &&
+      NS_SUCCEEDED(internal_GetHistogramEnumId(h->histogram_name().c_str(), &id)) &&
+      gHistograms[id].histogramType == nsITelemetry::HISTOGRAM_CATEGORICAL) {
+    nsAutoJSString label;
+    if (!label.init(cx, args[0])) {
+      JS_ReportError(cx, "Invalid string parameter");
       return false;
     }
 
-    if (!(args[0].isNumber() || args[0].isBoolean())) {
-      JS_ReportError(cx, "Not a number");
+    uint32_t labelId = 0;
+    if (NS_FAILED(gHistograms[id].label_id(NS_ConvertUTF16toUTF8(label).get(), &labelId))) {
+      JS_ReportError(cx, "Unknown label for categorical histogram");
       return false;
     }
 
-    if (!JS::ToInt32(cx, args[0], &value)) {
-      return false;
-    }
+    internal_HistogramAdd(*h, labelId);
+    return true;
+  }
+
+  // All other accumulations expect one numerical argument.
+  int32_t value = 0;
+  if (!args.length()) {
+    JS_ReportError(cx, "Expected one argument");
+    return false;
   }
 
-  if (internal_CanRecordBase()) {
-    internal_HistogramAdd(*h, value);
+  if (!(args[0].isNumber() || args[0].isBoolean())) {
+    JS_ReportError(cx, "Not a number");
+    return false;
   }
 
+  if (!JS::ToInt32(cx, args[0], &value)) {
+    JS_ReportError(cx, "Failed to convert argument");
+    return false;
+  }
+
+  internal_HistogramAdd(*h, value);
   return true;
 }
 
 bool
 internal_JSHistogram_Snapshot(JSContext *cx, unsigned argc, JS::Value *vp)
 {
   JS::CallArgs args = JS::CallArgsFromVp(argc, vp);
   JSObject *obj = JS_THIS_OBJECT(cx, vp);

--- a/toolkit/components/telemetry/gen-histogram-data.py
+++ b/toolkit/components/telemetry/gen-histogram-data.py
@@ -10,42 +10,66 @@ from shared_telemetry_utils import Strin
 
 import sys
 import histogram_tools
 import itertools
 
 banner = """/* This file is auto-generated, see gen-histogram-data.py.  */
 """
 
-def print_array_entry(output, histogram, name_index, exp_index):
+def print_array_entry(output, histogram, name_index, exp_index, label_index, label_count):
     cpp_guard = histogram.cpp_guard()
     if cpp_guard:
         print("#if defined(%s)" % cpp_guard, file=output)
-    print("  { %s, %s, %s, %s, %d, %d, %s, %s }," \
-        % (histogram.low(), histogram.high(),
-           histogram.n_buckets(), histogram.nsITelemetry_kind(),
-           name_index, exp_index, histogram.dataset(),
+    print("  { %s, %s, %s, %s, %d, %d, %s, %d, %d, %s }," \
+        % (histogram.low(),
+           histogram.high(),
+           histogram.n_buckets(),
+           histogram.nsITelemetry_kind(),
+           name_index,
+           exp_index,
+           histogram.dataset(),
+           label_index,
+           label_count,
            "true" if histogram.keyed() else "false"), file=output)
     if cpp_guard:
         print("#endif", file=output)
 
 def write_histogram_table(output, histograms):
-    table = StringTable()
+    string_table = StringTable()
+    label_table = []
+    label_count = 0
 
     print("const HistogramInfo gHistograms[] = {", file=output)
     for histogram in histograms:
-        name_index = table.stringIndex(histogram.name())
-        exp_index = table.stringIndex(histogram.expiration())
-        print_array_entry(output, histogram, name_index, exp_index)
+        name_index = string_table.stringIndex(histogram.name())
+        exp_index = string_table.stringIndex(histogram.expiration())
+
+        labels = histogram.labels()
+        label_index = 0
+        if len(labels) > 0:
+            label_index = label_count
+            label_table.append((histogram.name(), string_table.stringIndexes(labels)))
+            label_count += len(labels)
+
+        print_array_entry(output, histogram,
+                          name_index, exp_index,
+                          label_index, len(labels))
+    print("};\n", file=output)
+
+    strtab_name = "gHistogramStringTable"
+    string_table.writeDefinition(output, strtab_name)
+    static_assert(output, "sizeof(%s) <= UINT32_MAX" % strtab_name,
+                  "index overflow")
+
+    print("\nconst uint32_t gHistogramLabelTable[] = {", file=output)
+    for name,indexes in label_table:
+        print("/* %s */ %s," % (name, ", ".join(map(str, indexes))), file=output)
     print("};", file=output)
 
-    strtab_name = "gHistogramStringTable"
-    table.writeDefinition(output, strtab_name)
-    static_assert(output, "sizeof(%s) <= UINT32_MAX" % strtab_name,
-                  "index overflow")
 
 # Write out static asserts for histogram data.  We'd prefer to perform
 # these checks in this script itself, but since several histograms
 # (generally enumerated histograms) use compile-time constants for
 # their upper bounds, we have to let the compiler do the checking.
 
 def static_asserts_for_boolean(output, histogram):
     pass
@@ -84,16 +108,17 @@ def write_histogram_static_asserts(outpu
 // compile time, so that incorrect histogram definitions
 // give compile-time errors, not runtime errors.""", file=output)
 
     table = {
         'boolean' : static_asserts_for_boolean,
         'flag' : static_asserts_for_flag,
         'count': static_asserts_for_count,
         'enumerated' : static_asserts_for_enumerated,
+        'categorical' : static_asserts_for_enumerated,
         'linear' : static_asserts_for_linear,
         'exponential' : static_asserts_for_exponential,
         }
 
     for histogram in histograms:
         histogram_tools.table_dispatch(histogram.kind(), table,
                                        lambda f: f(output, histogram))
 

--- a/toolkit/components/telemetry/histogram_tools.py
+++ b/toolkit/components/telemetry/histogram_tools.py
@@ -102,23 +102,27 @@ symbol that should guard C/C++ definitio
         self._is_use_counter = name.startswith("USE_COUNTER2_")
         self.verify_attributes(name, definition)
         self._name = name
         self._description = definition['description']
         self._kind = definition['kind']
         self._cpp_guard = definition.get('cpp_guard')
         self._keyed = definition.get('keyed', False)
         self._expiration = definition.get('expires_in_version')
+        self._labels = definition.get('labels', [])
         self.compute_bucket_parameters(definition)
-        table = { 'boolean': 'BOOLEAN',
-                  'flag': 'FLAG',
-                  'count': 'COUNT',
-                  'enumerated': 'LINEAR',
-                  'linear': 'LINEAR',
-                  'exponential': 'EXPONENTIAL' }
+        table = {
+            'boolean': 'BOOLEAN',
+            'flag': 'FLAG',
+            'count': 'COUNT',
+            'enumerated': 'LINEAR',
+            'categorical': 'CATEGORICAL',
+            'linear': 'LINEAR',
+            'exponential': 'EXPONENTIAL',
+        }
         table_dispatch(self.kind(), table,
                        lambda k: self._set_nsITelemetry_kind(k))
         datasets = { 'opt-in': 'DATASET_RELEASE_CHANNEL_OPTIN',
                      'opt-out': 'DATASET_RELEASE_CHANNEL_OPTOUT' }
         value = definition.get('releaseChannelCollection', 'opt-in')
         if not value in datasets:
             raise DefinitionException, "unknown release channel collection policy for " + name
         self._dataset = "nsITelemetry::" + datasets[value]
@@ -128,17 +132,18 @@ symbol that should guard C/C++ definitio
         return self._name
 
     def description(self):
         """Return the description of the histogram."""
         return self._description
 
     def kind(self):
         """Return the kind of the histogram.
-Will be one of 'boolean', 'flag', 'count', 'enumerated', 'linear', or 'exponential'."""
+Will be one of 'boolean', 'flag', 'count', 'enumerated', 'categorical', 'linear',
+or 'exponential'."""
         return self._kind
 
     def expiration(self):
         """Return the expiration version of the histogram."""
         return self._expiration
 
     def nsITelemetry_kind(self):
         """Return the nsITelemetry constant corresponding to the kind of
@@ -168,51 +173,60 @@ associated with the histogram.  Returns 
     def keyed(self):
         """Returns True if this a keyed histogram, false otherwise."""
         return self._keyed
 
     def dataset(self):
         """Returns the dataset this histogram belongs into."""
         return self._dataset
 
+    def labels(self):
+        """Returns a list of labels for a categorical histogram, [] for others."""
+        return self._labels
+
     def ranges(self):
         """Return an array of lower bounds for each bucket in the histogram."""
-        table = { 'boolean': linear_buckets,
-                  'flag': linear_buckets,
-                  'count': linear_buckets,
-                  'enumerated': linear_buckets,
-                  'linear': linear_buckets,
-                  'exponential': exponential_buckets }
+        table = {
+            'boolean': linear_buckets,
+            'flag': linear_buckets,
+            'count': linear_buckets,
+            'enumerated': linear_buckets,
+            'categorical': linear_buckets,
+            'linear': linear_buckets,
+            'exponential': exponential_buckets,
+        }
         return table_dispatch(self.kind(), table,
                               lambda p: p(self.low(), self.high(), self.n_buckets()))
 
     def compute_bucket_parameters(self, definition):
         table = {
             'boolean': Histogram.boolean_flag_bucket_parameters,
             'flag': Histogram.boolean_flag_bucket_parameters,
             'count': Histogram.boolean_flag_bucket_parameters,
             'enumerated': Histogram.enumerated_bucket_parameters,
+            'categorical': Histogram.categorical_bucket_parameters,
             'linear': Histogram.linear_bucket_parameters,
-            'exponential': Histogram.exponential_bucket_parameters
-            }
+            'exponential': Histogram.exponential_bucket_parameters,
+        }
         table_dispatch(self.kind(), table,
                        lambda p: self.set_bucket_parameters(*p(definition)))
 
     def verify_attributes(self, name, definition):
         global always_allowed_keys
         general_keys = always_allowed_keys + ['low', 'high', 'n_buckets']
 
         table = {
             'boolean': always_allowed_keys,
             'flag': always_allowed_keys,
             'count': always_allowed_keys,
             'enumerated': always_allowed_keys + ['n_values'],
+            'categorical': always_allowed_keys + ['labels'],
             'linear': general_keys,
-            'exponential': general_keys
-            }
+            'exponential': general_keys,
+        }
         # We removed extended_statistics_ok on the client, but the server-side,
         # where _strict_type_checks==False, has to deal with historical data.
         if not self._strict_type_checks:
             table['exponential'].append('extended_statistics_ok')
 
         table_dispatch(definition['kind'], table,
                        lambda allowed_keys: Histogram.check_keys(name, definition, allowed_keys))
 
@@ -248,28 +262,16 @@ associated with the histogram.  Returns 
         # In the pipeline we don't have whitelists available.
         if whitelists is None:
             return
 
         for field in ['alert_emails', 'bug_numbers']:
             if field not in definition and name not in whitelists[field]:
                 raise KeyError, 'New histogram "%s" must have a %s field.' % (name, field)
 
-    def check_bug_numbers(self, name, definition):
-        # Use counters don't have any mechanism to add the bug numbers field.
-        if self._is_use_counter:
-            return
-
-        bug_numbers = definition.get('bug_numbers')
-        if not bug_numbers:
-            if whitelists is None or name in whitelists['bug_numbers']:
-                return
-            else:
-                raise KeyError, 'New histogram "%s" must have a bug_numbers field.' % name
-
     def check_field_types(self, name, definition):
         # Define expected types for the histogram properties.
         type_checked_fields = {
             "n_buckets": int,
             "n_values": int,
             "low": int,
             "high": int,
             "keyed": bool,
@@ -279,16 +281,17 @@ associated with the histogram.  Returns 
             "cpp_guard": basestring,
             "releaseChannelCollection": basestring,
         }
 
         # For list fields we check the items types.
         type_checked_list_fields = {
             "bug_numbers": int,
             "alert_emails": basestring,
+            "labels": basestring,
         }
 
         # For the server-side, where _strict_type_checks==False, we want to
         # skip the stricter type checks for these fields for dealing with
         # historical data.
         coerce_fields = ["low", "high", "n_values", "n_buckets"]
         if not self._strict_type_checks:
             def try_to_coerce_to_number(v):
@@ -348,16 +351,21 @@ associated with the histogram.  Returns 
                 definition['n_buckets'])
 
     @staticmethod
     def enumerated_bucket_parameters(definition):
         n_values = definition['n_values']
         return (1, n_values, n_values + 1)
 
     @staticmethod
+    def categorical_bucket_parameters(definition):
+        n_values = len(definition['labels'])
+        return (1, n_values, n_values + 1)
+
+    @staticmethod
     def exponential_bucket_parameters(definition):
         return (definition.get('low', 1),
                 definition['high'],
                 definition['n_buckets'])
 
 # We support generating histograms from multiple different input files, not
 # just Histograms.json.  For each file's basename, we have a specific
 # routine to parse that file, and return a dictionary mapping histogram

--- a/toolkit/components/telemetry/nsITelemetry.idl
+++ b/toolkit/components/telemetry/nsITelemetry.idl
@@ -17,22 +17,24 @@ interface nsITelemetry : nsISupports
 {
   /**
    * Histogram types:
    * HISTOGRAM_EXPONENTIAL - buckets increase exponentially
    * HISTOGRAM_LINEAR - buckets increase linearly
    * HISTOGRAM_BOOLEAN - For storing 0/1 values
    * HISTOGRAM_FLAG - For storing a single value; its count is always == 1.
    * HISTOGRAM_COUNT - For storing counter values without bucketing.
+   * HISTOGRAM_CATEGORICAL - For storing enumerated values by label.
    */
   const unsigned long HISTOGRAM_EXPONENTIAL = 0;
   const unsigned long HISTOGRAM_LINEAR = 1;
   const unsigned long HISTOGRAM_BOOLEAN = 2;
   const unsigned long HISTOGRAM_FLAG = 3;
   const unsigned long HISTOGRAM_COUNT = 4;
+  const unsigned long HISTOGRAM_CATEGORICAL = 5;
 
   /**
    * Scalar types:
    * SCALAR_COUNT - for storing a numeric value
    * SCALAR_STRING - for storing a string value
    * SCALAR_BOOLEAN - for storing a boolean value
    */
   const unsigned long SCALAR_COUNT = 0;

--- a/toolkit/components/telemetry/shared_telemetry_utils.py
+++ b/toolkit/components/telemetry/shared_telemetry_utils.py
@@ -30,16 +30,23 @@ class StringTable:
         if string in self.table:
             return self.table[string]
         else:
             result = self.current_index
             self.table[string] = result
             self.current_index += self.c_strlen(string)
             return result
 
+    def stringIndexes(self, strings):
+        """ Returns a list of indexes for the provided list of strings.
+        Adds the strings to the table if they are not in it yet.
+        :param strings: list of strings to put into the table.
+        """
+        return [self.stringIndex(s) for s in strings]
+
     def writeDefinition(self, f, name):
         """Writes the string table to a file as a C const char array.
 
         This writes out the string table as one single C char array for memory
         size reasons, separating the individual strings with '\0' characters.
         This way we can index directly into the string array and avoid the additional
         storage costs for the pointers to them (and potential extra relocations for those).
 

--- a/toolkit/components/telemetry/tests/unit/test_nsITelemetry.js
+++ b/toolkit/components/telemetry/tests/unit/test_nsITelemetry.js
@@ -198,16 +198,45 @@ add_task(function* test_count_histogram(
   do_check_eq(uneval(s.counts), uneval([1, 0, 0]));
   do_check_eq(s.sum, 1);
   h.add();
   s = h.snapshot();
   do_check_eq(uneval(s.counts), uneval([2, 0, 0]));
   do_check_eq(s.sum, 2);
 });
 
+add_task(function* test_categorical_histogram()
+{
+  let h1 = Telemetry.getHistogramById("TELEMETRY_TEST_CATEGORICAL");
+  for (let v of ["CommonLabel", "Label2", "Label3", "Label3", 0, 0, 1]) {
+    h1.add(v);
+  }
+  for (let s of ["", "Label4", "1234"]) {
+    Assert.throws(() => h1.add(s));
+  }
+
+  let snapshot = h1.snapshot();
+  Assert.equal(snapshot.sum, 6);
+  Assert.deepEqual(snapshot.ranges, [0, 1, 2, 3]);
+  Assert.deepEqual(snapshot.counts, [3, 2, 2, 0]);
+
+  let h2 = Telemetry.getHistogramById("TELEMETRY_TEST_CATEGORICAL_OPTOUT");
+  for (let v of ["CommonLabel", "CommonLabel", "Label4", "Label5", "Label6", 0, 1]) {
+    h2.add(v);
+  }
+  for (let s of ["", "Label3", "1234"]) {
+    Assert.throws(() => h2.add(s));
+  }
+
+  snapshot = h2.snapshot();
+  Assert.equal(snapshot.sum, 7);
+  Assert.deepEqual(snapshot.ranges, [0, 1, 2, 3, 4]);
+  Assert.deepEqual(snapshot.counts, [3, 2, 1, 1, 0]);
+});
+
 add_task(function* test_getHistogramById() {
   try {
     Telemetry.getHistogramById("nonexistent");
     do_throw("This can't happen");
   } catch (e) {
 
   }
   var h = Telemetry.getHistogramById("CYCLE_COLLECTOR");